Induced Four-Cycle Profiles Above Half Density

Definitions and mathematical statement

Adopt the conventional interpretation that graphs are finite, simple, and undirected; the supplied statement does not explicitly specify this convention. For a graph $G$ on $n\geq 4$ vertices, define its edge density and its induced four-cycle density by \[ p(G)=\frac{|E(G)|}{\binom{n}{2}},\qquad t_{\mathrm{ind}}(C_4,G)=\frac{N_{\mathrm{ind}}(C_4,G)}{\binom{n}{4}}, \] where $C_4$ is the cycle on four vertices and \[ N_{\mathrm{ind}}(C_4,G) =\left|\{S\subseteq V(G): |S|=4,\ G[S]\cong C_4\}\right|. \] Thus each qualifying four-element vertex set is counted once.

For each fixed $\xi\in[0,1]$, define the asymptotic maximum by \[ \Phi_{C_4}(\xi)= \sup\left\{ \limsup_{j\to\infty}t_{\mathrm{ind}}(C_4,G_j): |V(G_j)|\to\infty,\quad p(G_j)\to\xi \right\}. \] Using convergent edge densities makes the asymptotic question meaningful even when $\xi\binom{n}{2}$ is not an integer.

Problem. Determine $\Phi_{C_4}(\xi)$, equivalently the sharp asymptotic maximum number of induced copies of $C_4$ at prescribed limiting edge density $\xi$. In particular, for every fixed $\xi\in(1/2,1]$, is this maximum asymptotically attained by the construction referred to in the source as the extremal construction for the triangle-density problem? If $(H_j)$ denotes the intended construction at density $\xi$, the proposed attainment means \[ |V(H_j)|\to\infty,\qquad p(H_j)\to\xi, \qquad N_{\mathrm{ind}}(C_4,H_j) =\left(\Phi_{C_4}(\xi)+o(1)\right) \binom{|V(H_j)|}{4}. \] The supplied record does not describe $(H_j)$, state the triangle-density optimization precisely, or provide the claimed formula. Consequently, the construction-specific conjecture remains a source-dependent target rather than an explicit formula in this draft. The report context attributes the conjecture to Liu, Mubayi, and Reiher.

Short English statement

For each fixed edge density, determine the largest asymptotic proportion of four-vertex sets that induce a cycle. Above density $1/2$, the source asks whether the construction for the triangle-density problem attains this maximum. That construction and its proposed formula are not specified in the supplied record.

Sources

• Local UnsolvedMath registry, data/unsolvedmath/problems.json, permanent ID $30005116$, source problem code catalogue entry, title Induced Four-Cycle Profiles Above Half Density. This draft uses the supplied complete registry record.
• 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 record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions, and records proposed year 2022. Its retained report excerpt attributes the conjecture to Liu, Mubayi, and Reiher, with reference label [1], but does not reproduce the conjecture itself.
• Liu, Mubayi, and Reiher, The feasible region of induced graphs: https://doi.org/10.1016/j.jctb.2022.09.003. This is the supplied literature reference.
• Supplied dated literature curation, checked 2026-08-22: the record labels the problem partially solved and reports that the induced $C_4$ profile conjecture is proved at densities $1-1/k$, that general upper bounds exist, and that the claimed formula for every density above $1/2$ remains open. The range of $k$, upper bounds, and claimed formula are not supplied. This assessment is supplied dated curation derived from the OWR record, not independently verified here.
• The registry labels the statement corrected_verified and reports that the official Oberwolfach report was checked directly and that the cleaned statement restores definitions and removes extraction artifacts or source-dependent wording. These are supplied verification claims; this draft does not independently verify them or claim to have visited either source.