ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1156 · PARTIAL

Erdős problem 1156 — live-page audit, exact small cases, and the two missing bridges

Accessed 2026-07-27. Claim labels used below are:

0. Mandatory live-page gate

I fetched both the live problem page and its discussion thread in a Bright Data cloud browser, rather than by datacenter curl.

The gate result was:

Thus neither stop condition in the task applies.

Verbatim live statement

Let \(G\) be a random graph on \(n\) vertices, in which every edge is included independently with probability \(1/2\).

Is there some constant \(C\) such that that chromatic number \(\chi(G)\) is, almost surely, concentrated on at most \(C\) values?

Is it true that, if \(\omega(n)\to\infty\) sufficiently slowly, then for every function \(f(n)\) \[ > \mathbb P(|\chi(G)-f(n)|<\omega(n))<1/2 > \] if \(n\) is sufficiently large?

The duplicated “that” above is on the live page and has deliberately not been corrected.

Results listed on the live page

\[ \chi(G)\sim \frac{n}{2\log_2 n} \] with high probability.

\(\omega(n)/\sqrt n\to\infty\), there is \(f(n)\) such that \[ \mathbb P(|\chi(G)-f(n)|<\omega(n))\to1. \]

Scott, replaces that hypothesis by \(\omega(n)\log n/\sqrt n\to\infty\).

\(\omega(n)\), contains \(\chi(G)\) with probability tending to one, then for every \(c<1/4\) there are infinitely many \(n\) with \(\omega(n)>n^c\). Heckel and Riordan improved \(c<1/4\) to every \(c<1/2\).

The page itself warns that its open status is the site owner’s current belief and may miss literature.

The one live comment

The comment is explicitly user-supplied and unverified by the website. It reports the following six points:

  1. The strongest explicit lower bound, for infinitely many \(n\), is of order

\[ c\,\frac{\sqrt n\,\log\log n}{\log^3 n} \] for the length of a high-probability concentration interval.

  1. It is conjectured that along another infinite subsequence there is a

high-probability interval of length \[ C\,\frac{n^{1/4}}{\log^{7/4}n}. \]

  1. Consequently, the conjectured interval width “zigzags” between

\(n^{1/4+o(1)}\) and \(n^{1/2+o(1)}\); the comment points to Figure 2 and Conjectures 10–12 of Heckel–Riordan.

  1. It is not excluded that \(\chi(G)\) is one-point concentrated for almost

every \(n\), so the second question remains open.

  1. It is not excluded that \(\chi(G)\) is concentrated on two possibly distant

points for every \(n\), so the first question remains open. If the \(C\) values are required to be consecutive, the known interval theorem answers the question negatively.

  1. The comment links to lectures by Annika Heckel.

The comment writes [HeRe23]; the problem page and the actual paper use Heckel–Riordan, [HeRi23].

1. Primary-source literature audit

The following named sources exist and support the claims for which they are used.

Combinatorica 8 (1988), 49–55, DOI 10.1007/BF02122551, gives the fixed-\(p\) asymptotic used on the live page.

number on random graphs \(G_{n,p}\)*, Combinatorica 7 (1987), 121–129, DOI 10.1007/BF02579208, states concentration in \(\sqrt n\,\omega(n)\) consecutive integers for fixed \(p\), with \(\omega(n)\to\infty\).

graphs*, arXiv:0806.0178v2, gives the explanatory proof of Alon’s \(O(\sqrt n/\log n)\)-scale concentration.

graph*, JAMS 34 (2021), 245–260, arXiv:1906.11808v2, proves the \(n^{1/4-\varepsilon}\) consecutive-value result.

graph vary?*, JLMS 108 (2023), 1769–1815, arXiv:2103.14014v3, proves in Theorem 5 that every sequence of high-probability intervals has width \(>n^c\) for infinitely many \(n\), for every \(c<1/2\). The paper itself stresses that this gives no conclusion for any prescribed \(n\), let alone every \(n\), and does not exclude one-point concentration away from a sparse subsequence.

\(\sqrt n\log\log n/\log^3n\) bound is Theorem 8 of Heckel–Riordan conditional on their estimate (7). A. Heckel and K. Panagiotou, Colouring random graphs: Tame colourings, arXiv:2306.07253v3, Theorem 1.2, supplies an \(O(n^{0.99})\) estimate in the required bounded-colouring regime. Here the parameters in Theorem 8 satisfy \[ \frac{\mu_{a-1}}{\mu_a} =\frac{a\,2^{a-1}}{n-a+1} =\Theta(n/\log n), \] so \(\mu_a=\Theta(n/\log^2n)\) gives \(\mu_{a-1}=\Theta(n^2/\log^3n)\), within the range of the tame-colourings theorem. Also, \(O(n^{0.99})=o(n\log\log n/\log^4n)\), so the two papers together discharge that condition. This explains the unconditional wording in the live comment; attributing the complete implication to Heckel–Riordan alone suppresses this dependency.

number of random graphs*, Electronic Journal of Combinatorics 31 (2024), P1.44, arXiv:2201.00906v2, extends the upper-bound method to sparse and very dense \(p=p(n)\). For constant \(p\), its Theorem 3 recovers an \(O(\omega\sqrt n/\log n)\) high-probability interval. It gives neither anti-concentration on arbitrary separated values nor an eventual \(1/2\)-small-ball bound at \(p=1/2\), so it does not answer either question here.

I also searched arXiv by the exact dense-\(p=1/2\) concentration phrases, “bounded number of values”, “one-point concentrated”, and “Zigzag Conjecture”, including 2024–2026 results. (c) I found no later primary source claiming either question is solved. I did find work in the very-dense regime \(p\to1\), which is not the model in this problem. This is a targeted search miss, not a proof that no relevant paper exists.

2. Exact finite distribution, independently enumerated

Let

\[ a_{n,k}=\#\{G\text{ on the labelled vertex set }[n]:\chi(G)=k\}. \]

Since \(p=1/2\), the exact probability is \(a_{n,k}/2^{\binom n2}\).

Result

(d) The standalone checker recomputes the following table from scratch. Each tuple lists \((a_{n,1},\ldots,a_{n,n})\).

\(n\)\(2^{\binom n2}\)exact count tuple
11\((1)\)
22\((1,1)\)
38\((1,6,1)\)
464\((1,40,22,1)\)
51,024\((1,375,582,65,1)\)
632,768\((1,5{,}176,22{,}377,5{,}042,171,1)\)
72,097,152\((1,103{,}236,1{,}353{,}810,605{,}545,34{,}139,420,1)\)

(d) Every displayed row is log-concave:

\[ a_{n,k}^2\ge a_{n,k-1}a_{n,k+1}, \]

and hence unimodal. This is only a finite computation, not a conjecture promoted to a theorem for general \(n\).

For scale, (d) at \(n=7\),

\[ \mathbb P(\chi=3)=\frac{1{,}353{,}810}{2{,}097{,}152} =0.645546913\ldots, \]

and the two values \(3,4\) have total mass

\[ \frac{1{,}959{,}355}{2{,}097{,}152}=0.934293270\ldots. \]

The optional independent \(n=8\) prefix gives (d)

\[ (a_{8,1},a_{8,2},a_{8,3}) =(1,2{,}922{,}445,134{,}222{,}308) \]

and

\[ \sum_{k\ge4}a_{8,k}=131{,}290{,}702. \]

In particular,

\[ \mathbb P(\chi(G_{8,1/2})=3) =\frac{134{,}222{,}308}{268{,}435{,}456} =0.5000170618\ldots. \]

This near-half finite coincidence has no demonstrated asymptotic significance.

Why the enumeration is exact

(a) Number the \(\binom n2\) possible edges and encode a labelled graph by its edge-mask \(g\). Enumerate every set partition \(\pi\) of \([n]\) once by a restricted-growth string. Let \(W_\pi\) be the mask of pairs lying in the same block. Then

\[ \pi\text{ is a proper colouring of }g \quad\Longleftrightarrow\quad g\mathbin{\&}W_\pi=0. \]

For each \(k\), take the union over all partitions into exactly \(k\) nonempty blocks. A colouring using fewer than \(k\) colours can be refined to exactly \(k\) nonempty colour classes (for \(k\le n\)), so this union is exactly the set \(U_k\) of graphs with \(\chi\le k\). Thus

\[ a_{n,k}=|U_k\setminus U_{k-1}|. \]

The code represents a set of graph-masks by a Python integer whose \(g\)-th bit records membership. Starting with bit zero, for every allowed edge position \(e\), the operation cube |= cube << (1 << e) adds that edge to every graph already represented. Induction on the allowed edges proves that the final set bits are exactly all submasks of the allowed-edge mask. There is no SAT solver, graph library, random sampling, floating-point classification, or stored graph catalogue.

3. Two exact all-\(n\) tail formulas

These formulas are not in the typical \(\chi\asymp n/\log n\) regime, but they provide closed-form checks on two complete slices of the distribution.

The two-colour slice

Let \(B_n\) be the number of labelled bipartite graphs on \([n]\), with \(B_0=1\), and set

\[ A_n=\sum_{j=0}^n\binom nj\,2^{j(n-j)}. \]

Then (a)

\[ B_n=\frac12\left( A_n-\sum_{j=1}^{n-1}\binom nj B_jB_{n-j} \right), \qquad a_{n,2}=B_n-1\quad(n\ge2). \]

Proof: \(A_n\) counts a graph together with an ordered proper two-colouring: choose the \(j\) vertices of the first colour and then choose any subset of the \(j(n-j)\) cross-edges. Equivalently, a bipartite graph with \(c\) connected components contributes \(2^c\). The sum \(\sum_j\binom njB_jB_{n-j}\) also counts every bipartite graph \(2^c\) times, by assigning each entire connected component to one of two labelled parts. Isolating the \(j=0,n\) terms gives the recurrence. Finally, only the empty graph among bipartite graphs has chromatic number one.

(a), arithmetically checked by the script: for \(n=2,\ldots,10\),

\[ a_{n,2}= 1,6,40,375,5176,103236,2922445,116011230,6433447396. \]

The \(n-1\)-colour slice

For every \(n\ge3\), (a)

\[ a_{n,n-1}=n(2^{n-1}-1)-\binom n2. \]

Proof: put \(H=\overline G\). A saving of two colours is possible exactly when \(H\) contains a triangle (one three-vertex colour class) or two vertex-disjoint edges (two two-vertex classes). Therefore \(\chi(G)=n-1\) exactly when \(H\) is nonempty and has neither structure. All edges of such an \(H\) must share one common vertex: otherwise two are disjoint, while three pairwise-intersecting edges without a common vertex form a triangle. Thus \(H\) is a nonempty subgraph of a star. Counting by the star centre gives \(n(2^{n-1}-1)\); each one-edge graph was counted twice, so subtract \(\binom n2\). The formula matches every applicable row of the independent table.

4. A clean bridge that would settle the first question

Write

\[ p_n(k)=\mathbb P(\chi(G_{n,1/2})=k) \]

and let \(A_C(n)\) be the sum of its \(C\) largest atoms. Under the standard “with high probability” reading of the first question, (a) a positive answer is exactly the assertion that \(A_C(n)\to1\) for some fixed \(C\).

Unimodality bridge

(b) Proposition (new reduction, modulo Heckel–Riordan Theorem 5). If \(k\mapsto p_n(k)\) is unimodal for all sufficiently large \(n\), then the answer to the first question is no.

Proof. In a finite unimodal sequence, a set of \(C\) largest entries can be chosen consecutively: starting from a mode, repeatedly take the larger of the two adjacent unused entries. Consequently, if \(A_C(n)\to1\), there are intervals of \(C\) consecutive integers containing \(\chi\) with probability tending to one. Heckel–Riordan Theorem 5 says that for every \(c<1/2\), any such sequence of high-probability intervals has width \(>n^c\) for infinitely many \(n\). A constant-width sequence is a contradiction.

Log-concavity implies unimodality, so the exact rows through \(n=7\) test a genuinely sufficient structural condition. (c) Nothing here proves eventual unimodality or log-concavity. The needed uniform lemma is precisely one that forbids a bounded collection of tall, widely separated peaks.

5. An exact reformulation of the second question

For any integer-valued random variable \(Y_n\), define its concentration function

\[ Q_n(r)=\sup_{x\in\mathbb R}\mathbb P(|Y_n-x|<r). \]

Because \(Y_n\) has finite support here, the supremum is a maximum.

(a) Diagonal lemma. Under the natural existential meaning of “\(\omega(n)\to\infty\) sufficiently slowly”, the second question is equivalent to the following fixed-window statement:

For every fixed integer \(R\ge1\), there is \(N_R\) such that \(Q_n(R)<1/2\) for all \(n\ge N_R\).

Proof. If a diverging \(\omega(n)\) works, then eventually \(\omega(n)\ge R\), and monotonicity in the radius gives \(Q_n(R)\le Q_n(\omega(n))<1/2\).

Conversely, replace the thresholds \(N_R\) by a strictly increasing sequence \(\widetilde N_R\ge\max(R,N_1,\ldots,N_R)\), and define

\[ \omega(n)=\max\{R:\widetilde N_R\le n\}. \]

Then \(\omega(n)\to\infty\), while the fixed-window hypothesis gives \(Q_n(\omega(n))<1/2\).

This isolates the missing theorem exactly: one needs eventual anti-concentration below one half for every fixed window. Heckel–Riordan instead control intervals carrying probability close to one on an unavoidable infinite subsequence. The probability threshold \((1/2\) versus \(0.9\) or \(1-o(1))\) and the quantifier on \(n\) \((\)all sufficiently large versus infinitely many\()\) are both essential.

6. Why interval machinery alone cannot bridge the gap

The live comment’s “two far-apart points” obstruction is not merely verbal. There is an explicit abstract model with all the basic monotonicity and bounded-difference properties used by vertex-exposure concentration.

Let \(n\) and \(L\) be even, let \(X_1,\ldots,X_n\) be independent fair bits, let \(S=\sum_iX_i\), and put

\[ t=\frac{n-L}{2},\qquad F_{n,L}=\min\{L,\max\{0,S-t\}\}. \]

Then (a):

  1. \(F_{n,L}\) is coordinatewise nondecreasing.
  2. Changing one bit changes \(F_{n,L}\) by at most one.
  3. If \(L\to\infty\) and \(L=o(\sqrt n)\), then

\[ \mathbb P(F_{n,L}\in\{0,L\})\to1, \qquad \mathbb P(F_{n,L}=0) =\mathbb P(F_{n,L}=L)\to\frac12. \]

  1. Nevertheless, every interval carrying (say) \(0.9\) probability has

diameter at least \(L\), for all sufficiently large \(n\).

For (3), the only non-endpoint values occur when \((n-L)/2<S<(n+L)/2\), a strip of fewer than \(L\) binomial atoms. Each atom is at most the central binomial probability \(O(n^{-1/2})\), so the strip has probability \(O(L/\sqrt n)=o(1)\). Reflection \(S\mapsto n-S\) makes the two endpoint probabilities equal. An interval of diameter \(<L\) can contain at most one endpoint, proving (4).

The checker also verifies an exact finite instance, \(n=100000,L=20\): over \(95\%\) of the mass is on the two endpoints, while even granting every interior value to an interval containing one endpoint leaves its mass below \(0.9\).

For chromatic number, altering all edges incident with one vertex changes \(\chi\) by at most one: both graphs lie between \(\chi(G-v)\) and \(\chi(G-v)+1\). Thus (a) monotonicity, one-coordinate Lipschitzness, and a lower bound on concentration-interval width cannot by themselves rule out bounded support on separated values. Any proof of the first question needs additional graph-specific control of the shape of \(p_n(k)\); the unimodality proposition identifies one sufficient form of that control.

7. Reproduction, resource audit, and limits

The standalone verifier is runs/erdos1156_wave6w_reverify.py.

Run:

python runs/erdos1156_wave6w_reverify.py
python runs/erdos1156_wave6w_reverify.py --n8-prefix

Observed on this VM:

26.8 CPU seconds, 180,520 KiB peak RSS;

The bitset has \(2^{\binom n2}\) bits before transient copies: 32 MiB for \(n=8\), 8 GiB for \(n=9\), and 4 TiB for \(n=10\). An earlier attempt at the full \(n=8\) row was stopped after 72.4 CPU seconds and 276,600 KiB RSS rather than spending further CPU. A naive \(n=9\) three-colour prefix extrapolates to roughly 6 core-hours and at least 8 GiB base memory (with much larger transient memory traffic); a full row would cost more. No such heavy job was run. Isomorph-free software can extend the exploratory table cheaply, but I have not promoted those outputs here because they would not be independently reproduced by this from-scratch checker.

Most importantly, no finite table supplies the required uniform asymptotic step. The exact remaining mathematical targets are:

(eventual unimodality is one clean sufficient lemma);

PARTIAL: Exact labelled distributions through n=7 (plus the n=8 chi<=3 prefix), two all-n tail formulas, an eventual-unimodality reduction for question 1, and an exact fixed-window reformulation for question 2 are verified; the two uniform asymptotic lemmas remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger