781 citations
- Weizmann Institute of ScienceIL21 papers
- University of FreiburgDE14 papers
- European Organization for Nuclear ResearchCH13 papers
- Pennsylvania State UniversityUS13 papers
- Heidelberg UniversityDE11 papers
- Massachusetts Institute of TechnologyUS11 papers
- Princeton UniversityUS11 papers
- University of BonnDE11 papers
- Universität HamburgDE10 papers
- University of ChicagoUS10 papers
- Columbia UniversityUS9 papers
- Technion – Israel Institute of TechnologyIL9 papers
8 papers · 2 filters
High degree graphs contain large-star factors
Noga Alon, Nicholas Wormald
We show that any finite simple graph with minimum degree contains a spanning star forest in which every connected component is of size at least . This sett…
Economical toric spines via Cheeger's Inequality
Noga Alon, Bo'az Klartag
Let denote the graph whose set of vertices is , where two distinct vertices are adjacent iff they are either equal or adjacent in $C_m…
Regular induced subgraphs of a random graph
Michael Krivelevich, Benny Sudakov, Nicholas Wormald
An old problem of Erdős, Fajtlowicz and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on n vertices. Motivated by this problem, w…
On the random satisfiable process
Michael Krivelevich, Benny Sudakov, Dan Vilenchik
In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas -- randomly permute all 2^k\binom{n}{k} possible clauses over the va…
Fast winning strategies in Avoider-Enforcer games
Dan Hefetz, Michael Krivelevich, Miloš Stojaković +1
In numerous positional games the identity of the winner is easily determined. In this case one of the more interesting questions is not {\em who} wins but rather {\em how fast} can…
Hamiltonicity thresholds in Achlioptas processes
Michael Krivelevich, Eyal Lubetzky, Benny Sudakov
In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on n labeled vertices. At each round we are pres…