Sparse Random Graphs Avoiding Non-Bipartite Subgraphs

Definitions and mathematical statement

The supplied problem asks for density thresholds and typical structure of uniformly random $H$-free graphs with $m$ edges, where $H$ is nonbipartite. A graph is nonbipartite if its vertices cannot be partitioned into two sets such that every edge has one endpoint in each set.

The record does not specify the number of vertices, the graph conventions, the asymptotic regime, or the structural properties whose thresholds are sought. Consequently, it does not determine a unique precise threshold problem. The following describes a possible conventional framework, conditional on assumptions that require confirmation.

Assume that graphs are finite, simple, undirected, and labelled; that $H$ is fixed independently of the number $n$ of vertices; and that $H$-free means containing no subgraph isomorphic to $H$, without requiring that subgraph to be induced. For a positive integer $n$ and an integer $m$ satisfying $0\le m\le\binom{n}{2}$, put \[ \mathcal F_H(n,m)=\left\{G:V(G)=\{1,\ldots,n\},\ |E(G)|=m,\ G\text{ contains no subgraph isomorphic to }H\right\}. \] Whenever $\mathcal F_H(n,m)\ne\varnothing$, let $G_{n,m}^{(H)}$ have the uniform distribution on this family, so that \[ \Pr\left(G_{n,m}^{(H)}=G\right)=\frac{1}{|\mathcal F_H(n,m)|} \qquad\text{for every }G\in\mathcal F_H(n,m). \] In this framework, a proposed structural property $\mathcal P_n$ is typical along a sequence $m=m(n)$ if \[ \lim_{n\to\infty}\Pr\left(G_{n,m(n)}^{(H)}\in\mathcal P_n\right)=1, \] with the sampling family nonempty for all sufficiently large $n$.

Requested determination, with unresolved scope. For a general nonbipartite graph $H$, determine the density regimes and the structural properties that hold typically for the uniformly sampled $H$-free graph with $m$ edges, together with the thresholds between the intended structural regimes. The source does not identify those properties or regimes, specify whether density means edge count, edge density $m/\binom{n}{2}$, or another normalization, or state whether threshold means an order of magnitude, a sharp transition, or an exact asymptotic constant. These choices, as well as the conditional graph conventions above, must be resolved before this request can be expressed as a specific quantified threshold assertion.

Short English statement

For a nonbipartite forbidden graph $H$, describe how the typical structure of a uniformly random $H$-free graph changes with its number $m$ of edges. The supplied record leaves the vertex count, sampling conventions, limiting regime, and target structural transitions unspecified; the displayed model is therefore conditional and requires human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002465$, title Sparse Random Graphs Avoiding Non-Bipartite Subgraphs, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The recorded proposed year is 2014; no individual proposer is supplied.
• Source report and literature-source label "Original OWR record": Combinatorics (2014), Oberwolfach Reports, DOI 10.4171/owr/2014/01, pp. 5--90. https://doi.org/10.4171/owr/2014/01. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. No problem-specific page or excerpt is supplied.
• Supplied literature-source label "Turán problems for paths and cycles": https://www.sciencedirect.com/science/article/pii/S0097316514001204.
• Supplied literature-source label "Linear hypergraph cycles": https://arxiv.org/abs/1302.2387.
• Literature assessment dated 2026-08-21: the supplied curation labels the problem open and states that known exact formulas cover several loose and linear path and cycle families, while a broad pair of extremal-number questions remains unresolved. This is supplied dated curation, not independently verified. Its terminology and subject do not match the random-graph question stated here, so its applicability is unresolved. The supplied background itself requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports a manual semantic, typographic, and LaTeX review of its cleanup. This is a supplied editorial claim, not independent verification of the formulation, references, or mathematical status.