From the 1 of 30 linked papers with an AI index.
11 papers · 1 filter
Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree
Sahar Diskin, Michael Krivelevich
We provide sufficient conditions for a regular graph of growing degree , guaranteeing a phase transition in its random subgraph similar to that of when $p\cdo…
On Independent Spanning Trees in Random and Pseudorandom Graphs
Nemanja DraganiÄ, Keith Frankston, Michael Krivelevich +2
In 1989, Zehavi and Itai conjectured that every -connected graph contains independent spanning trees rooted at any prescribed vertex . That is, for each vertex , the u…
On the edge expansion of random polytopes
Asaf Ferber, Michael Krivelevich, Marcelo Sales +1
A -polytope in is the convex hull of a subset of . The graph of a polytope is the graph whose vertices are the zero-dimensional faces of and…
Minors in small-set expanders
Michael Krivelevich, Rajko Nenadov
We study large minors in small-set expanders. More precisely, we consider graphs with vertices and the property that every set of size at most expands by a factor of…
The Hamilton cycle space of random regular graphs and randomly perturbed graphs
Dan Hefetz, Michael Krivelevich
The cycle space of a graph , denoted , is a vector space over , spanned by all incidence vectors of edge-sets of cycles of . If has vertices, the…
The Hamilton cycle space of random graphs
Dan Hefetz, Michael Krivelevich
The cycle space of a graph , denoted , is a vector space over , spanned by all incidence vectors of edge-sets of cycles of . If has vertices, the…