Upper tails for subgraph counts in random graphs

By Svante Janson, K. Oleszkiewicz, Andrzej Rucinski. 2004

133 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/b55f8344123a63ecaff107e0cd9e98b96901279a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Applications of Stein's method for concentration inequalities (2009, methodology): “The best upper bounds to date were obtained by Kim and Vu [27] (triangles) and Janson, Oleszkiewicz, and Ruciński [25] (general subgraph counts).”
Moment inequalities for functions of independent random variables (2005, result): “Recent work by Kim and Vu [21] show that better, and in a sense optimal, upper bounds can be obtained with some more work; see also [19] for related recent results.”
Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order (2013, background): “In [35] the Authors prove that for every ε > 0 such that P ( YH (n, p) ≥ (1+ ε)EYH (n, p) ) > 0,”
Combinatorial theorems in sparse random sets (2010, background): “Thankfully, most of the hard work has already been done for us by Janson, Ruciński and, in one paper, Oleszkiewicz [28], [29], [30], [31], [32].”
Upper tails via high moments and entropic stability (2019, methodology): “ll codimension, where, crucially, the average value of X on each of these subcubes is at least (1 + ")E[X]. The proof uses a variant of the moment argument of Janson, Oleszkiewicz, and Ruciski [38]. Lemma 3.6. Let Y be a random variable taking values in f0;1gN and let X= X(Y) be a nonzero poly”
Upper tails and independence polynomials in random graphs (2015, methodology): “[17] S. Janson and A. Ruciński.”
An introduction to large deviations for random graphs (2016, unknown): “[28] who showed that if p ≥ n logn, then e1 (2)p(2) log(1/p) ≤ P(Tn,p ≥ (1 + δ)E(Tn,p)) ≤ e2 (2)p(2) , where c1(δ) and c2(δ) are constants that depend only on δ.”
On the KŁR conjecture in random graphs (2013, background): “We also believe that a variant of part (i) of Theorem 1.6 may be derivable from the work of Saxton and Thomason [78], though they have not stated it in these terms.”
Large deviations of subgraph counts for sparse Erdős–Rényi graphs (2018, background): “04, Theorems 1.2, 1.5], we have that for all K>1 there exists c(K,F) >0 such that for all N≥ v(F) and all N−1/∆(F) <p<1, P(injF(A) ≥ KEinjF(A)) ≤ exp −c(K,F)N2p∆(F) . (Note that while [JOR04] considers subgraph counts rather than injective homomorphism counts, the two diﬀer by a ﬁxed c”
Nonlinear large deviations (2014, background): “By [18, Theorem 1.2 and Theorem 1.5], (48) where ∆ is the maximum degree of H , provided that p ≥ N − 1 / ∆ and N is suﬃciently large.”
Random sampling of 3-colorings in Z 2 (2004, background): “up to a factor logn) for any fixed " 0, see [ 17 ].”
Metrics for sparse graphs (2007, result): “(For early results of this type see Bollobás [3] and Ruciński [35]; for more recent, much stronger, results see Janson [26] and Janson, Oleszkiewicz and Ruciński [28].”