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.

2. 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}. \]

3. 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.

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

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

5. 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.

6. 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 |

|---:|---:|---|

| 1 | 1 | \((1)\) |

| 2 | 2 | \((1,1)\) |

| 3 | 8 | \((1,6,1)\) |

| 4 | 64 | \((1,40,22,1)\) |

| 5 | 1,024 | \((1,375,582,65,1)\) |

| 6 | 32,768 | \((1,5{,}176,22{,}377,5{,}042,171,1)\) |

| 7 | 2,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|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. \]

4. 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

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 \(

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:

  • default full \(n\le7\) audit: 3.9 seconds;
  • default plus the exact \(n=8\), \(\chi\le3\) prefix: 48.1 seconds wall,

26.8 CPU seconds, 180,520 KiB peak RSS;

  • all assertions passed.

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:

  • for question 1, rule out a bounded number of separated high peaks

(eventual unimodality is one clean sufficient lemma);

  • for question 2, prove \(Q_n(R)<1/2\) eventually for every fixed \(R\).

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