B. DeMarco

activity

20102015

most citedUpper tails for triangles

63 citations · 86 across the 4 of their papers we have counts for

collaborators

6 papers

math.PR2015★ 9 cited

Turán's Theorem for random graphs

Bobby DeMarco, Jeff Kahn

For a graph $G$ , denote by $t_{r} (G)$ (resp. $b_{r} (G)$ ) the maximum size of a $K_{r}$ -free (resp. $(r - 1)$ -partite) subgraph of $G$ . Of course $t_{r} (G) \geq b_{r} (G)$ for any $G$ , and Turán…

math.CO2014

Modular statistics for subgraph counts in sparse random graphs

Bobby DeMarco, Jeff Kahn, Amanda Redlich

Answering a question of Kolaitis and Kopparty, we show that, for given integer $q > 1$ and pairwise nonisomorphic connected graphs $G_{1} ... G_{k}$ , if $p = p (n)$ is such that $\Pr(G_{n,p}…

math.CO2012

Graph decomposition and parity

Bobby DeMarco, Amanda Redlich

Motivated by a recent extension of the zero-one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph $G…

math.PR2012

On the triangle space of a random graph

Bobby DeMarco, Arran Hamm, Jeff Kahn

Settling a first case of a conjecture of M. Kahle on the homology of the clique complex of the random graph $G = G_{n, p}$ , we show, roughly speaking, that (with high probability) the…

math.PR2012★ 14 cited

Mantel's Theorem for random graphs

Bobby DeMarco, Jeff Kahn

For a graph $G$ , denote by $t (G)$ (resp. $b (G)$ ) the maximum size of a triangle-free (resp. bipartite) subgraph of $G$ . Of course $t (G) \geq b (G)$ for any $G$ , and a classic result…

math.PR2010★ 63 cited

Upper tails for triangles

Bobby DeMarco, Jeff Kahn

With $ξ$ the number of triangles in the usual (Erdős-Rényi) random graph $G (m, p)$ , $p > 1/ m$ and $η > 0$ , we show (for some $C_{η} > 0$ ) $$\Pr(ξ> (1+η)\E ξ) < \exp[-C_η\min{m^2p^2\log(1/p)…