From the 1 of 18 linked papers with an AI index.
19 papers
Rigidity of expanders and pseudorandom graphs
Michael Krivelevich, Alan Lew, Peleg Michaeli
A graph is called -rigid if, for a generic embedding of its vertices in , the only continuous motions of the vertices preserving the distances between al…
Efficient Hamilton covers and linear arboricity of random graphs
Nemanja DraganiÄ, Michael Krivelevich
The paper proves that the minimum possible size of a Hamilton cover in binomial random graphs matches the trivial lower bound across a wide range of edge probabilities, and also sh…
On graphs whose cycle space is spanned by their Hamilton cycles
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 ver…
Supercritical Site Percolation on Regular Graphs
Sahar Diskin, Michael Krivelevich, Itay Markbreit
We consider site (vertex) percolation on -regular graphs, for both constant-degree and growing-degree cases. We give sufficient, and relatively tight, conditions for the emergen…
Combinatorial sufficient conditions for graph rigidity and applications to random graphs
Michael Krivelevich, Alan Lew, Peleg Michaeli
A graph is called -rigid if, for a generic embedding of its vertices in , every edge-length preserving continuous motion of the vertices preserves the di…
Subgraph discrepancies in the complete graph
Micha Christoph, Lior Gishboliner, Michael Krivelevich
Given a 2-edge-coloring , the discrepancy of a subgraph is defined as . ErdÅs, Füredi,…