Petersen-Graph Counts in Sparse Pseudorandom Graphs

Definitions and mathematical statement

The supplied problem concerns an asymptotic family of graphs. The formulation below uses the standard conventions of finite simple undirected graphs, ordinary (not necessarily induced) subgraph copies, and uniform discrepancy over all vertex subsets. These conventions are not fully specified in the supplied record and require confirmation against the source.

Write $[n]=\{1,\ldots,n\}$. Let $G_n$ have vertex set $[n]$, and define its edge density by \[ p_n=\frac{2|E(G_n)|}{n(n-1)}. \] For possibly overlapping subsets $A,B\subseteq[n]$, use the ordered incidence convention \[ e_{G_n}(A,B)=\left|\{(a,b)\in A\times B:\{a,b\}\in E(G_n)\}\right|. \] Thus an edge with both endpoints in $A\cap B$ contributes twice. Say that $G_n$ is $C_4$-free if it contains no subgraph isomorphic to the cycle of length four, whether induced or not.

Define the Petersen graph $P$ to have vertex set $\binom{[5]}{2}$, with two vertices adjacent exactly when the corresponding two-element subsets are disjoint. It has ten vertices and fifteen edges. Let \[ X_P(G)=\frac{1}{|\operatorname{Aut}(P)|} \left|\{\phi:V(P)\hookrightarrow V(G): \{\phi(u),\phi(v)\}\in E(G)\text{ for every }\{u,v\}\in E(P)\}\right| \] count its ordinary subgraph copies. Let $G(n,p)$ be the random graph on $[n]$ in which each unordered pair of distinct vertices is independently an edge with probability $p$. Then \[ \mathbb E X_P(G(n,p)) =\frac{(n)_{10}}{|\operatorname{Aut}(P)|}p^{15}, \qquad (n)_{10}=n(n-1)\cdots(n-9). \]

A precise interpretation of the supplied question is the following. For every fixed $c_0>0$, does there exist $c=c(c_0)>0$ such that every sequence $(G_n)_{n\to\infty}$ of $C_4$-free graphs satisfying \[ p_n\ge c_0 n^{-1/2} \quad\text{for all sufficiently large }n, \qquad \frac{1}{p_n n^2} \max_{A,B\subseteq[n]} \left|e_{G_n}(A,B)-p_n|A||B|\right|\longrightarrow0 \] also satisfies, for all sufficiently large $n$, \[ X_P(G_n)\ge c\,\mathbb E X_P(G(n,p_n)) =c\,\frac{(n)_{10}}{|\operatorname{Aut}(P)|}p_n^{15}? \] Here the threshold for sufficiently large $n$ may depend on the sequence. The source does not explicitly specify whether the comparison constant may depend on the implicit constant in $p\gtrsim n^{-1/2}$; the displayed quantifiers permit that dependence. The uniform interpretation of the little-oh condition and the counting conventions above are explicit interpretations, not independently verified source details.

Short English statement

Must every sufficiently large $C_4$-free graph with edge density at least a fixed positive multiple of $n^{-1/2}$, and uniformly negligible discrepancy relative to $pn^2$, contain at least a fixed positive fraction of the expected Petersen-graph count in $G(n,p)$? The precise counting conventions and dependence of the comparison constant need source confirmation. The supplied registry labels the problem open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry: supplied complete source record, permanent ID $30005117$, title "Petersen-Graph Counts in Sparse Pseudorandom Graphs," exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2022.
• Supplied report citation: Combinatorics, Probability and Computing (2023), Oberwolfach Reports, pp. 1165--1237, DOI 10.4171/owr/2022/22. https://doi.org/10.4171/owr/2022/22. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source, labeled "Conlon, Fox, Sudakov, and Zhao, sparse regularity": https://doi.org/10.1112/jlms.12500.
• Supplied literature source, labeled "official OWR report": https://publications.mfo.de/bitstream/handle/mfo/3964/OWR_2022_22.pdf?isAllowed=y&sequence=4.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and reports finding no proof or counterexample under the stated $C_4$-free and discrepancy hypotheses. This is supplied dated curation, not an independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and supplies a claim that the official report was checked directly and extraction artifacts were removed. That verification claim is part of the supplied record; no source visit or independent verification is asserted here.