Pith. sign in

On the $H$-space of a random graph

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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$.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2025 1

verdicts

ACCEPT 1

roles

background 1

polarities

unclear 1

representative citing papers

citing papers explorer

Showing 1 of 1 citing paper.

  • When does a tree activate the random graph? math.CO · 2025-07-08 · accept · none · ref 25 · internal anchor

    The critical probability for the existence of a K3-activating spanning tree in G(n,p) is p = n^{-1/3-o(1)}.