14 papers
Cliques in minimally globally rigid graphs
Julien Portier
We show that every minimally generically globally rigid graph in which contains a subgraph isomorphic to is itself isomorphic to , confirming a con…
Reconstructing a giant component of a point set in
Julien Portier
Let be a finite set with and suppose we are given each pairwise distance independently with probability . We show that if , for s…
Tight bounds for expected propagation time of probabilistic zero forcing
Mehdi Jelassi, Julien Portier, Rik Sarkar
We study the probabilistic zero forcing process, a probabilistic variant of the classical zero forcing process. We show that for every connected graph on vertices, there ex…
Nearly tight bounds for MaxCut in hypergraphs
Oliver Janzer, Julien Portier
An -cut of a -uniform hypergraph is a partition of its vertex set into parts, and the size of the cut is the number of edges which have at least one vertex in each part.…
Approximate Itai-Zehavi conjecture for random graphs
Lawrence Hollom, Lyuben Lichev, Adva Mond +2
A famous conjecture by Itai and Zehavi states that, for every -vertex-connected graph and every vertex in , there are spanning trees of such that, for every v…
Monotonicity and decompositions of random regular graphs
Lawrence Hollom, Lyuben Lichev, Adva Mond +2
In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameter…