Monochromatic Structures below Random Density

Definitions and mathematical statement

The supplied record combines two questions. The arithmetic-progression question admits the following precise formulation under an explicit counting convention; the graph-structure question remains underspecified.

For each integer $n\geq 1$, let $[n]=\{1,\ldots,n\}$. A two-colouring is a map $\chi:[n]\to\{0,1\}$. Adopt the convention that a three-term arithmetic progression is a triple $(a,a+d,a+2d)$ with integers $a\geq 1$, $d\geq 1$, and $a+2d\leq n$, counted once in increasing order. Define \[ M_n(\chi)=\left|\left\{(a,d)\in{\mathbb{Z}}^2:a\geq1,\ d\geq1,\ a+2d\leq n,\ \chi(a)=\chi(a+d)=\chi(a+2d)\right\}\right| \] and \[ m(n)=\min_{\chi:[n]\to\{0,1\}}M_n(\chi). \] The arithmetic-progression problem is to determine the asymptotically minimal count $m(n)$ as $n\to\infty$, including its leading coefficient if it has the form \[ m(n)=c n^2+o(n^2). \] This formulation does not assert that such a constant $c$ exists. The source does not specify its counting or density normalization. The convention above excludes constant progressions and identifies the two orientations of a progression; it must be checked against the original report before numerical constants are compared.

The other source question asks whether an analogue of the "quadratic-structure phenomenon" for two-colourings with fewer than the random density of monochromatic $K_4$'s holds for graph colourings. Here $K_4$ denotes the complete graph on four vertices. The supplied record does not define the quoted phenomenon, the objects coloured in its premise, the graph-colouring model in its conclusion, the random comparison model, or the structural conclusion and its quantifiers. Consequently, this part cannot be converted into a precise mathematical assertion from the supplied evidence alone; no structural theorem or conjectural implication is being supplied here.

Short English statement

Determine the smallest possible number of monochromatic three-term arithmetic progressions in a two-colouring of $\{1,\ldots,n\}$, asymptotically as $n\to\infty$, using the stated counting convention. The accompanying question about quadratic structure and monochromatic $K_4$'s needs additional definitions from its source. Both parts remain statement-only drafts requiring human mathematical review.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $30002033$, title "Monochromatic Structures below Random Density", source problem code catalogue entry, collection "Oberwolfach Reports Open Problems". No individual proposer is supplied; the proposed year is recorded as 2012.
• Supplied report citation: Mini-Workshop: Hypergraph Turán Problem (2013), Oberwolfach Reports, pp. 1149--1182, DOI 10.4171/owr/2012/19. https://doi.org/10.4171/owr/2012/19. The record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. Its citation year 2013 differs from its proposed-year and year-tag value 2012; this discrepancy has not been resolved.
• Supplied literature reference: Parrilo--Robertson--Saracino. https://doi.org/10.1016/j.jcta.2007.03.006.
• Supplied literature reference: Greenwood--Kariv--Williams. https://arxiv.org/abs/2301.00336.
• Supplied literature reference: Oberwolfach report. https://ems.press/content/serial-article-files/46390?nt=1.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. The supplied status is "open". The assessment states that the asymptotic minimum density of monochromatic three-term progressions in two-colourings is undetermined and that known bounds and restricted-class optimality results leave the general problem open. The background describes this as dated literature triage derived from the supplied Oberwolfach curation and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified, with a supplied note reporting manual semantic, typographic, and LaTeX review of a meaning-preserving cleanup. This is a source-record qualification, not independent verification of the formulation, literature, or mathematical status.