Source author record

Bobby DeMarco

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR Discrete Mathematics

Catalog footprint

Research overview

7works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Graph decomposition and parity

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(n,p)$ . We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo $q$ . We determine the asymptotic distribution of all fixed two-component graphs in $G(n,p)$ for all $q$ , and we give infinite families of many-component graphs with a uniform asymptotic distribution for all $q$ . We also prove a negative result, that no simple proof of uniform asymptotic distribution for arbitrary graphs exists.

preprint2015arXiv

Modular statistics for subgraph counts in sparse random graphs

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}\supseteq G_i)\to 1$ $\forall i$ , then, with $ξ_i$ the number of copies of $G_i$ in $G_{n,p}$ , $(ξ_1...ξ_k)$ is asymptotically uniformly distributed on ${\bf Z}_q^k$ .

preprint2015arXiv

Turán's Theorem for random graphs

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's Theorem says that equality holds for complete graphs. With $G_{n,p}$ the usual ("binomial" or "Erdős-Rényi") random graph, we show: For each fixed r there is a C such that if $p=p(n) > Cn^{-\tfrac{2}{r+1}}\log^{\tfrac{2}{(r+1)(r-2)}}n,$ then $\Pr(t_r(G_{n,p})=b_r(G_{n,p}))\rightarrow 1$ as $n\rightarrow\infty$ . This is best possible (apart from the value of $C$ ) and settles a question first considered by Babai, Simonovits and Spencer about 25 years ago.

preprint2012arXiv

Mantel's Theorem for random graphs

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 of Mantel from 1907 (the first case of Turán's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e. for what $p=p(n)$ ) is the "Erdős-Rényi" random graph $G=G(n,p)$ likely to satisfy $t(G) = b(G)$ ? We show that this is true if $p>C n^{-1/2} \log^{1/2}n$ for a suitable constant $C$ , which is best possible up to the value of $C$ .

preprint2012arXiv

On the triangle space of a random graph

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 triangles of $G$ span its cycle space whenever each of its edges lies in a triangle (which happens (w.h.p.) when $p$ is at least about $\sqrt{(3/2)\ln n/n}$ , and not below this unless $p$ is very small.) We give two related proofs of this statement, together with a relatively simple proof of a fundamental "stability" theorem for triangle-free subgraphs of $G_{n,p}$ , originally due to Kohayakawa, Łuczak and Rödl, that underlies the first of our proofs.

preprint2012arXiv

Upper Tails for Cliques

With $ξ_{k}=ξ_{k}^{n,p}$ the number of copies of $K_k$ in the usual (Erdős-Rényi) random graph $G(n,p)$ , $p\geq n^{-2/(k-1)}$ and $η>0$ , we show when $k>1$ $$\Pr(ξ_k> (1+η)\E ξ_k) < \exp [-\gO_{η,k} \min\{n^2p^{k-1}\log(1/p), n^kp^{\binom{k}{2}}\}].$$ This is tight up to the value of the constant in the exponent.

preprint2011arXiv

Upper tails for triangles

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),m^3p^3}].$$ This is tight up to the value of $C_η$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Bobby DeMarco

Research overview

Is this your work?

7 publications

Graph decomposition and parity

Modular statistics for subgraph counts in sparse random graphs

Turán's Theorem for random graphs

Mantel's Theorem for random graphs

On the triangle space of a random graph

Upper Tails for Cliques

Upper tails for triangles

See the researcher in context

Building this map preview