8 citations · 9 across the 6 of their papers we have counts for
9 papers
Greedy maximal independent sets via local limits
Michael Krivelevich, Tamás Mészáros, Peleg Michaeli +1
The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the c…
Additive Approximation of Generalized Turán Questions
Noga Alon, Clara Shikhelman
For graphs and , and a family of graphs let denote the maximum possible number of copies of in an -free subgrap…
A generalized Turán problem in random graphs
Wojciech Samotij, Clara Shikhelman
We study the following generalization of the Turán problem in sparse random graphs. Given graphs and , let be the random variable that co…
Semi-random graph process
Omri Ben-Eliezer, Dan Hefetz, Gal Kronenberg +3
We introduce and study a novel semi-random multigraph process, described as follows. The process starts with an empty graph on vertices. In every round of the process, one vert…
-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
Noga Alon, Clara Shikhelman
We consider the structure of -free subgraphs of graphs with high minimal degree. We prove that for every there exists an so that the following holds. For eve…
Many cliques in -free subgraphs of random graphs
Noga Alon, Alexandr Kostochka, Clara Shikhelman
For two fixed graphs and let be the random variable counting the maximum number of copies of in an -free subgraph of the random graph . We s…
On the Converse of Talagrand's Influence Inequality
Saleet Klein, Amit Levi, Muli Safra +2
In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of nu…
Packing a randomly edge-colored random graph with rainbow -outs
Asaf Ferber, Gal Kronenberg, Frank Mousset +1
Let be a graph on vertices and let be a fixed positive integer. We denote by $\mathcal G_{\text{$k$-out}}(G)$ the probability space consisting of subgraphs of where…
Thresholds and expectation-thresholds of monotone properties with small minterms
Ehud Friedgut, Jeff Kahn, Clara Shikhelman
Let be a finite set, let , and let denote a random binomial subset of where every element of is taken to belong to the subset independently with prob…