Sparse Quadrilateral Removal at the Extremal Threshold

Definitions and mathematical statement

A quadrilateral is interpreted here as a cycle of length four on four distinct vertices, without requiring it to be induced. For a finite simple undirected graph $G$, let $\mathcal C_4(G)$ be the set of its distinct four-cycle subgraphs, counted without a choice of starting vertex or orientation, and put $q_4(G)=|\mathcal C_4(G)|$. The supplied record does not explicitly specify the graph convention or the cycle-counting convention; these standard interpretations require confirmation.

An edge-disjoint quadrilateral decomposition is a family $\mathcal D\subseteq\mathcal C_4(G)$ such that \[ E(G)=\bigcup_{C\in\mathcal D}E(C),\qquad E(C)\cap E(C')=\varnothing\quad(C\ne C'). \] The cycles in $\mathcal D$ may share vertices. Relative to this decomposition, an additional quadrilateral means an element of $\mathcal C_4(G)\setminus\mathcal D$; it need not be edge-disjoint from the decomposition cycles.

First question. Under these conventions, is it true that \[ \begin{gathered} \forall\varepsilon>0\ \exists n_0(\varepsilon)\in{\mathbb{N}}\ \forall n\in{\mathbb{N}},\ n\ge n_0(\varepsilon),\ \forall G,\ \forall\mathcal D:\\ \left[|V(G)|=n,\ \mathcal D\text{ is an edge-disjoint quadrilateral decomposition of }G, \ |\mathcal D|\ge\varepsilon n^{3/2}\right] \ \Longrightarrow\ \mathcal C_4(G)\setminus\mathcal D\ne\varnothing? \end{gathered} \] Here the graph quantifier ranges over finite simple undirected graphs. The interpretation of "another" as outside the specified decomposition is explicit and requires source confirmation.

Quantitative question. The source additionally asks whether such a graph contains at least $\delta n^2$ quadrilaterals for some $\delta>0$. A natural precise interpretation is \[ \begin{gathered} \forall\varepsilon>0\ \exists\delta=\delta(\varepsilon)>0\ \exists n_0=n_0(\varepsilon)\in{\mathbb{N}}\ \forall n\in{\mathbb{N}},\ n\ge n_0,\ \forall G,\ \forall\mathcal D:\\ \left[|V(G)|=n,\ \mathcal D\text{ is an edge-disjoint quadrilateral decomposition of }G, \ |\mathcal D|\ge\varepsilon n^{3/2}\right] \ \Longrightarrow\ q_4(G)\ge\delta n^2. \end{gathered} \] This displayed quantifier order is provisional: the source does not explicitly state whether $\delta$ may depend on $\varepsilon$, or whether the sufficiently large threshold may be enlarged for the quantitative question. The count here includes the decomposition cycles. Both assertions are questions, not established conclusions.

Short English statement

The problem asks whether sufficiently many edge-disjoint four-cycles covering a graph's edges force a further four-cycle outside that decomposition, and whether they force at least $\delta n^2$ four-cycles in total. The threshold for the given decomposition is $\varepsilon n^{3/2}$. Graph conventions and the dependence of $\delta$ require confirmation. The supplied record labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30001674$, source problem code catalogue entry, title "Sparse Quadrilateral Removal at the Extremal Threshold," in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2011 and does not identify an individual proposer.
• Supplied report citation: Combinatorics (2011), Oberwolfach Reports, DOI 10.4171/owr/2011/01, pp. 5--83. Source report and literature-source label "Oberwolfach problem statement": https://doi.org/10.4171/owr/2011/01. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature-source label "modern removal-lemma survey": https://www.ibs.re.kr/ecopro/wp-content/uploads/2025/08/IBS_2025Summer_removal_lemma.pdf.
• Literature checked at: 2026-08-21. The supplied dated curation labels the problem open and assesses the sparse $C_4$-removal assertion as conjectural, stating that later removal-lemma results do not establish this sparse $n^{3/2}$ threshold. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment; time-sensitive status and cited claims require independent verification.
• The supplied statement-status label is corrected_verified; its stated verification consists of enclosing TeX notation in math delimiters without changing the mathematical content. This records a formatting correction and does not establish mathematical correctness.