On the $H$-space of a random graph

Abstract

The edge space $\mathcal{E}(G)$ of a graph $G$ is the vector space ${\mathbb{F}}_2^{E(G)}$ with members naturally identified with subgraphs of $G$, and the $H$-space is the subspace ${\mathcal{C}}_H(G)$ of $\mathcal{E}(G)$ spanned by copies of the graph $H$. We are interested in when the random graph $G=G_{n,p}$ is likely to satisfy \[\mathcal{C}_H(G) = \mathcal{W}_H(G),\] where ${\mathcal{W}}_H(G)$ takes one of four natural values, depending on the value of ${\mathcal{C}}_H(K_n)$. We show that for strictly $2$-balanced $H$, w.h.p. the above equality holds whenever every edge of $G$ is in a copy of $H$.

arXiv admin note: text overlap with arXiv:1610.01276