betaFeedback

WorksMathematics

A counterexample to Erdős problem 108 via arc graphs

Abstract

For every positive integer MM, we construct a finite triangle-free graph GG of chromatic number at least MM in which every ordinary four-cycle-free subgraph is 6-colorable. Consequently, no chromatic threshold forces a subgraph of girth at least five and chromatic number at least seven, which gives a negative answer to Erdős problem 108. The proof uses a multipartite random graph of bounded acyclic outdegree in which every subgraph under a prescribed degree cap is 4-colorable. An arc-graph construction raises the host chromatic number while partitioning each four-cycle-free subgraph into a part controlled by the degree cap and a forest. The linked Lean verification covers the original negative answer. The written proof includes the triangle-free strengthening.

Introduction

The high-girth subgraph problem of Erdős and Hajnal asks whether, for every pair of integers r≥4r \ge4 and k≥2k \ge2, there is an integer f(k,r)f(k,r) such that every graph of chromatic number at least f(k,r)f(k,r) contains a subgraph of girth at least rr and chromatic number at least kk. The question appears as Problem 108 in Bloom’s catalogue [1] and is formalized in the Formal Conjectures library [2].

Throughout this paper, a subgraph may be obtained by deleting vertices and edges. A four-cycle-free graph excludes a copy of C4C_4 as an ordinary subgraph. A four-cycle with chords is still forbidden.

Theorem 1.1. For every integer M≥1M \ge1, there is a finite nonempty triangle-free simple graph GG such that χ(G)≥M\chi(G) \ge M and every four-cycle-free subgraph HH of GG satisfies χ(H)≤6\chi(H) \le6.

Corollary 1.2. There is no integer ff such that every graph of chromatic number at least ff contains a subgraph of girth at least five and chromatic number at least seven. In particular, the assertion in Erdős problem 108 is false.

Proof. Given a proposed threshold ff, apply Theorem 1.1 with M=max⁡{1,f}M = \max\{1, f\}. Every subgraph of girth at least five is four-cycle-free, so its chromatic number is at most six. □\square

The construction starts with the multipartite random model used by Janzer, Steiner and Sudakov in their work on chromatic number and regular subgraphs [3]. We adapt its separated-part-size method to obtain a statement with two independent parameters, a chromatic parameter qq and a degree cap KK. The outdegree bound depends only on qq. This permits us to choose KK after fixing that bound and then apply an arc-graph argument. All estimates needed for this adaptation are proved here.

Section 2 gives the arc-graph lemmas. Section 3 constructs the base graph, including the size estimates and both probability bounds. Section 4 proves Theorem 1.1. Section 5 describes the formal proof and its verification records.

Notation. All graphs used in the construction are finite and simple. We write eF(X)e_F(X) for the number of edges in F[X]F[X], and eF(X,Y)e_F(X,Y) for the number of edges between disjoint vertex sets XX and YY. The maximum degree of a graph is denoted by Δ\Delta. A graph is 3-degenerate if every nonempty subgraph has a vertex of degree at most three. Such a graph is 4-colorable. For an acyclic digraph DD, let U(D)U(D) be its underlying undirected graph. Forests have infinite girth in the written proof.

Arc graphs and bounded-degree selections

Definition 2.1. Let DD be an acyclic orientation of a simple graph. Its arc graph L(D)L(D) has the arcs of DD as vertices, with two vertices adjacent precisely when the corresponding arcs concatenate. Thus (u,v)(u,v) and (v,w)(v,w) are adjacent. We orient this edge from (u,v)(u,v) to (v,w)(v,w).

Fix a topological ordering of DD. Along every oriented edge of L(D)L(D), the tail of the corresponding arc strictly increases in this ordering. The displayed orientation of L(D)L(D) is therefore acyclic.

Lemma 2.2. The graph L(D)L(D) is triangle-free.

Proof. An acyclic orientation of a triangle has vertices a,b,ca,b,c with edges a→ba \to b, b→cb \to c and a→ca \to c. If a=(u,v)a=(u,v) and b=(v,w)b=(v,w), the edge b→cb \to c makes the tail of cc equal to ww, whereas a→ca \to c makes it equal to vv. Hence v=wv=w, contradicting the fact that bb is an arc of a simple graph. □

Lemma 2.3. If L(D)L(D) is tt-colorable, then U(D)U(D) is 2t2^t-colorable. In particular,

χ(U(D))≤2χ(L(D)).(1)\chi(U(D)) \le2^{\chi(L(D))}. \tag*{(1)}

Proof. Fix a proper coloring of L(D)L(D) with colors in {1,…,t}\{1,\ldots,t\}. Assign to each vertex vv of DD the set of colors occurring on arcs directed out of vv. If (u,v)(u,v) has color cc, the set at uu contains cc. Every arc directed out of vv is adjacent to (u,v)(u,v), so the set at vv excludes cc. Adjacent vertices of U(D)U(D) therefore receive distinct subsets of the tt-element color set. □

Lemma 2.4 (Arc selection). Suppose that DD is acyclic, has maximum outdegree at most dd, and every subgraph of U(D)U(D) with maximum degree at most

Kd=d+(d2)(2)K_d = d + \binom{d}{2} \tag*{(2)}

is aa-colorable. Then every four-cycle-free subgraph of L(D)L(D) is (a+2)(a+2)-colorable.

Proof. Let H⊆L(D)H \subseteq L(D) be four-cycle-free, and restrict the natural orientation to HH. Partition its vertex set into SS and TT, where SS consists of the arc vertices having at least two outgoing neighbors in HH, and TT consists of the remaining arc vertices.

Fix a vertex vv of DD. For every incoming arc (u,v)(u,v) belonging to SS, choose an unordered pair of its outgoing neighbors in HH. These neighbors are arcs of the form (v,w)(v,w). Two distinct incoming arcs cannot receive the same pair, since the two incoming arcs and the two chosen outgoing arcs would form a four-cycle. Consequently at most

(dD+(v)2)≤(d2)\binom{d_D^+(v)}{2} \le\binom{d}{2}

incoming arcs at vv belong to SS.

Let DSD_S retain precisely the arcs of DD corresponding to vertices in SS. Its outdegrees are at most dd and its indegrees are at most (d2)\binom{d}{2}. Hence Δ(U(DS))≤Kd\Delta(U(D_S)) \le K_d. By hypothesis there is a proper aa-coloring cc of U(DS)U(D_S). Color an arc vertex (u,v)∈S(u,v) \in S by c(u)c(u). If (u,v)(u,v) and (v,w)(v,w) are adjacent in H[S]H[S], the edge uvuv belongs to U(DS)U(D_S), so these two arc vertices receive different colors.

The inherited orientation of H[T]H[T] is acyclic and every vertex has outdegree at most one. Such a graph is a forest. In an acyclic orientation any undirected cycle has a source on that cycle and therefore a vertex with two outgoing edges. Color H[T]H[T] with two colors disjoint from the first palette. This gives an (a+2)(a+2)-coloring of HH. □

Remark 2.5. The partition and the selected graph DSD_S depend on the edge-deleted subgraph HH. The argument works for ordinary subgraphs. The indegree bound applies to the selected digraph DSD_S.

The multipartite base graph

Theorem 3.1. For every pair of integers q≥2q \ge2 and K≥4K \ge4, there is a finite simple graph FF with an acyclic orientation DD such that

  1. χ(F)>2q\chi(F) > 2q,

  2. the maximum outdegree of DD is at most 64q2−164q^2-1, and

  3. every subgraph J⊆FJ \subseteq F with Δ(J)≤K\Delta(J) \le K is 33-degenerate, and hence 44-colorable.

In particular, the outdegree bound in (2) is independent of KK.

The random model and explicit sizes

Put

C=64q2,h=2(K+1),A=16CK(K+1),b=h+2.(3)C = 64q^2,\qquad h = 2(K+1),\qquad A = 16CK(K+1),\qquad b = h+2. \tag*{(3)}

Choose the positive integer RR, then define BB and the part sizes by

R=(16C)h32h+1A+3A+8C+2,(4)R = (16C)^h3^{2h+1}A+3A+8C+2, \tag*{(4)}
B=bC+1,ni=RB−bi+1(0≤i<C).(5)B = b^{C+1},\qquad n_i = R^{B-b^{i+1}}\quad(0 \le i < C). \tag*{(5)}

Take disjoint sets V0,…,VC−1V_0,\ldots,V_{C-1} with ∣Vi∣=ni|V_i|=n_i and no edges inside a part. For every v∈Viv\in V_i and every j>ij>i, independently choose a uniformly distributed vertex w(v,j)∈Vjw(v,j)\in V_j and insert the edge vw(v,j)vw(v,j). Orient each edge from its earlier part to its later part. This orientation is acyclic and has maximum outdegree at most C−1C-1.

Write N=∑iniN=\sum_i n_i and N0=RBN_0=R^B. The following elementary estimates are the reason for the choice of exponents.

Lemma 3.2. The sizes in (5) satisfy

ni≥R≥8C,Rnj≤ni(i<j),(6)n_i\ge R\ge8C,\qquad Rn_j\le n_i\quad(i<j), \tag*{(6)}
N≤Cn0≤An0,N≤N0,(7)N\le Cn_0\le An_0,\qquad N\le N_0, \tag*{(7)}
∑j>inj≤ni,∑j≥inj≤2ni.(8)\sum_{j>i}n_j\le n_i,\qquad\sum_{j\ge i}n_j\le2n_i. \tag*{(8)}

For 1≤i<C1\le i<C, put L=ni−1L=n_{i-1}. For every integer xx with 1≤x≤Ani1\le x\le An_i, one also has

3x≤L,32h+1N0hxLh+1≤(16C)−h.(9)3x\le L,\qquad\frac{3^{2h+1}N_0^h x}{L^{h+1}}\le(16C)^{-h}. \tag*{(9)}

Proof. Since b>1b>1 and i<Ci<C, the exponent B−bi+1B-b^{i+1} is a positive integer. For i<ji<j the two exponents differ by at least one, which proves (6). The sizes are decreasing. Since R≥CR\ge C and each ni≤RB−1n_i\le R^{B-1}, we obtain N≤CRB−1≤RB=N0N\le CR^{B-1}\le R^B=N_0. The other inequalities in (7) use A≥CA\ge C. Moreover, Rnj≤niRn_j\le n_i for each j>ij>i, so R∑j>inj≤Cni≤RniR\sum_{j>i}n_j\le Cn_i\le Rn_i, proving (8).

Fix i≥1i\ge1. Since R≥3AR\ge3A, the successive-size inequality gives 3x≤3Ani≤Rni≤ni−1=L3x\le3An_i\le Rn_i\le n_{i-1}=L. Next, the identity b=h+2b=h+2 gives

(h+1)(B−bi)−hB−(B−bi+1)=bi.(h+1)(B-b^i)-hB-(B-b^{i+1})=b^i.

Thus Lh+1=RbiN0hni≥RN0hniL^{h+1}=R^{b^i}N_0^h n_i\ge RN_0^h n_i. It follows that

32h+1N0hxLh+1≤32h+1AR≤(16C)−h,\frac{3^{2h+1}N_0^h x}{L^{h+1}}\le\frac{3^{2h+1}A}{R}\le(16C)^{-h},

where the last inequality is immediate from (4). □\square

The deterministic cut

Consider the following local sparsity condition on a realization of FF:

X⊆V0∪⋯∪Vi−1,0<∣X∣≤Ani⇒eF(X)<(1+1/h)∣X∣.(10)X \subseteq V_0 \cup\cdots\cup V_{i-1}, \quad0 < |X| \le An_i \quad\Rightarrow\quad e_F(X) < (1 + 1/h)|X|. \tag*{(10)}

For i=0i=0 the condition is vacuous.

Lemma 3.3. If (10) holds for every ii, then every subgraph of FF with maximum degree at most KK is 33-degenerate.

Proof. Suppose that J⊆FJ \subseteq F has minimum degree at least four and maximum degree at most KK, and let s=∣V(J)∣>0s = |V(J)| > 0. By (7), there is an index ii with s≤Anis \le An_i. Choose the largest such index. Partition V(J)V(J) into X,Y,ZX,Y,Z, according as the part index is less than, equal to, or greater than ii. If i=C−1i=C-1, then Z=∅Z=\varnothing. Otherwise, maximality gives Ani+1<sAn_{i+1}<s, and the decreasing sizes give ∣Z∣≤Cni+1<Cs/A=s/(16K(K+1))|Z| \le Cn_{i+1}<Cs/A=s/(16K(K+1)). In either case we may use the weaker bound

∣Z∣<2s16K(K+1).(11)|Z| < \frac{2s}{16K(K+1)}. \tag*{(11)}

Each vertex of XX has at most one neighbor in ViV_i, while the degree cap gives at most K∣Y∣K|Y| edges incident with YY. Hence eJ(X,Y)≤∣X∣e_J(X,Y) \le|X| and eJ(X,Y)≤K∣Y∣e_J(X,Y) \le K|Y|. Taking the weighted average with weights K/(K+1)K/(K+1) and 1/(K+1)1/(K+1) yields

eJ(X,Y)≤KK+1(∣X∣+∣Y∣)≤KK+1s.(12)e_J(X,Y) \le\frac{K}{K+1}(|X|+|Y|) \le\frac{K}{K+1}s. \tag*{(12)}

The set YY is independent. At most K∣Z∣K|Z| edges have an endpoint in ZZ, and the minimum-degree assumption gives e(J)≥2se(J) \ge2s. Therefore

eJ(X)≥2s−eJ(X,Y)−K∣Z∣>(2−KK+1−18(K+1))s=(1+78(K+1))s>(1+1/h)∣X∣.(13)\begin{aligned} e_J(X) &\ge2s-e_J(X,Y)-K|Z| \\ &> \left(2-\frac{K}{K+1}-\frac{1}{8(K+1)}\right)s \\ &= \left(1+\frac{7}{8(K+1)}\right)s > (1+1/h)|X|. \tag*{(13)} \end{aligned}

In particular XX is nonempty, and ∣X∣≤s≤Ani|X| \le s \le An_i. Since eJ(X)≤eF(X)e_J(X) \le e_F(X), this contradicts (10). Thus there is no subgraph with all degrees between four and KK. Every subgraph of a graph of maximum degree at most KK still has maximum degree at most KK, so every such graph is 33-degenerate. □

The probability of a dense earlier set

Lemma 3.4. The probability that (10) fails for some ii is at most 1/81/8.

Proof. Fix i≥1i \ge1 and 1≤x≤Ani1 \le x \le An_i, and put L=ni−1L=n_{i-1}, m=⌈(1+1/h)x⌉m=\lceil(1+1/h)x\rceil, and δ=1/(16C)\delta=1/(16C). For a specified collection of mm distinct possible edges among the earlier parts, either two edges demand different choices from the same pair (v,j)(v,j), in which case the event is impossible, or they impose mm independent choices. Every target part has size at least LL, so the probability that all the specified edges occur is at most L−mL^{-m}.

There are at most (N0x)\binom{N_0}{x} possible sets XX of size xx, and at most (x2m)\binom{x^2}{m} choices of the required edges. Thus the probability that an earlier set of size xx violates (10) is at most

(N0x)(x2m)L−m≤(3N0x)x(3xL)m.(14)\binom{N_0}{x}\binom{x^2}{m}L^{-m}\le\left(\frac{3N_0}{x}\right)^x\left(\frac{3x}{L}\right)^m. \tag*{(14)}

Here we used (nk)≤(en/k)k≤(3n/k)k\binom{n}{k}\le(en/k)^k\le(3n/k)^k for k≥1k\ge1, together with m≥xm\ge x. If the prescribed number of edges is impossible, the same estimate holds with probability zero.

Set a=3N0/xa=3N_0/x and z=3x/Lz=3x/L. By Lemma 3.2, 0<z≤10<z\le1. Since hm≥(h+1)xhm\ge(h+1)x, raising the right side of (14) to the integer power hh gives

(axzm)h≤(ahzh+1)x=(32h+1N0hxLh+1)x≤δhx.(a^x z^m)^h \le(a^h z^{h+1})^x = \left(\frac{3^{2h+1}N_0^h x}{L^{h+1}}\right)^x \le\delta^{hx}.

It follows that (14) is at most δx\delta^x. Since δ≤1/2\delta\le1/2, summing over the possible positive sizes gives a failure probability at most

∑x≥1δx=δ1−δ≤2δ≤18C\sum_{x\ge1}\delta^x=\frac{\delta}{1-\delta}\le2\delta\le\frac{1}{8C}

for a fixed ii. Summing over at most CC indices proves the result.

The probability of a heavy independent set

Assign weight 1/ni1/n_i to each vertex of ViV_i. For a vertex set II, write

pi(I)=∣I∩Vi∣ni,w(I)=∑j=0C−1pj(I).(15)p_i(I)=\frac{|I\cap V_i|}{n_i},\qquad w(I)=\sum_{j=0}^{C-1}p_j(I). \tag*{(15)}

The total vertex weight is CC.

Lemma 3.5. The probability that FF has an independent set II with w(I)≥C/(2q)w(I)\ge C/(2q) is at most 1/81/8.

Proof. Suppose that w(I)≥C/(2q)w(I)\ge C/(2q). Choose the first index ii with pi(I)≥1/(4q)p_i(I)\ge1/(4q). Such an index exists. Earlier parts contribute less than C/(4q)C/(4q) and pi(I)≤1p_i(I)\le1, so

∑j>ipj(I)>C4q−1=16q−1≥15q.(16)\sum_{j>i}p_j(I)>\frac{C}{4q}-1=16q-1\ge15q. \tag*{(16)}

The part of II in indices at least ii is still independent and preserves both inequalities. We may therefore count only sets in this suffix.

Fix a suffix set II satisfying these inequalities, and put t=∣I∩Vi∣≥ni/(4q)t=|I\cap V_i|\ge n_i/(4q). For II to be independent, all choices from its tt vertices in ViV_i to each later part VjV_j must avoid I∩VjI\cap V_j. These choices are independent, so

P(I is independent)≤∏j>i(1−pj(I))t≤exp⁡(−t∑j>ipj(I))≤e−3ni.(17)\mathbb{P}(I\text{ is independent})\le\prod_{j>i}(1-p_j(I))^t\le\exp\left(-t\sum_{j>i}p_j(I)\right)\le e^{-3n_i}. \tag*{(17)}

Indeed, (16) and t≥ni/(4q)t\ge n_i/(4q) give an exponent of absolute value at least 15ni/415n_i/4. By (8), the entire suffix has at most 2ni2n_i vertices. There are therefore at most 22ni≤e2ni2^{2n_i}\le e^{2n_i} possible suffix sets. The union bound and (17) give probability at most e−nie^{-n_i} for a witness with a fixed first heavy index ii. Finally, ni≥8Cn_i\ge8C and eni≥1+nie^{n_i}\ge1+n_i imply e−ni≤1/(8C)e^{-n_i}\le1/(8C). Summing over all ii proves the lemma.

Proof of Theorem 3.1. Lemmas 3.4 and 3.5 bound the two failure probabilities by 1/81/8 each. Their sum is less than one, so there is a realization satisfying (10) in which every independent set has weight less than C/(2q)C/(2q). Lemma 3.3 proves (3), and the orientation of the construction proves (2).

If FF were 2q2q-colorable, its color classes would be independent sets of total weight strictly less than 2q⋅C/(2q)=C2q\cdot C/(2q)=C. But the color classes partition a vertex set of weight CC. This contradiction proves χ(F)>2q\chi(F)>2q, completing (1).

Proof of the main theorem

Proof of Theorem 1.1. Fix M≥1M\ge1 and put

q=2M+2,C=64q2,d=C−1,K=d+(d2).(18)q=2^M+2,\qquad C=64q^2,\qquad d=C-1,\qquad K=d+\binom{d}{2}. \tag*{(18)}

These parameters satisfy q≥2q\ge2 and K≥4K\ge4. Apply Theorem 3.1 with this pair (q,K)(q,K) to obtain F=U(D)F=U(D). Every subgraph of FF with maximum degree at most KK is 44-colorable, and the maximum outdegree of DD is at most dd. The choice of KK is legitimate because the outdegree bound in Theorem 3.1 is independent of KK. Set G=L(D)G = L(D). Lemma 2.4, with a=4a = 4, shows that every four-cycle-free subgraph of GG is 6-colorable. Lemma 2.2 shows that GG is triangle-free. If χ(G)≤M\chi(G) \le M, then Lemma 2.3 gives

χ(F)≤2χ(G)≤2M<2q,\chi(F) \le2^{\chi(G)} \le2^M < 2q,

contrary to Theorem 3.1. Thus χ(G)>M\chi(G) > M. The graph GG is finite, and this inequality also ensures that it is nonempty. □

Remark 4.1. List the vertices of DD in a topological order. The map sending an arc to the ordered pair of its endpoint indices identifies L(D)L(D) with an induced subgraph of the canonical shift graph on ordered pairs (i,j)(i,j) with i<ji < j, where (i,j)(i,j) is adjacent to (j,k)(j,k). The proof of Corollary 1.2 uses only the conclusions of Theorem 1.1.

Lean formalization and verification

The accompanying source edition [5, 6] formalizes the arc-graph construction and the negative answer. The theorem Bounty.arc_counterexample_family gives a nonempty arc-graph witness for each M∈NM \in\mathbb{N}, with chromatic number at least MM and with every four-cycle-free subgraph 6-colorable. The triangle-free conclusion of Theorem 1.1 follows from Lemma 2.2 in the written proof. The checked Bounty.target proves the negation of the original Erdos108.erdos_108 type.

The formalization represents vertices of the multipartite model as pairs (i,x)(i,x) with i<Ci < C and x<nix < n_i, in lexicographic order. A sample is a finite dependent product of choices. Unused choices into earlier parts are retained so that the sample space is rectangular. Uniform probabilities are finite-set cardinalities divided by the cardinality of the sample space. The existence argument uses exact finite counting and real-valued estimates in Lean.

The predicate FourCycleFree excludes two distinct vertices having two distinct common neighbors. In a simple graph this is exactly the absence of an ordinary four-cycle. The type SimpleGraph.Subgraph includes both vertex and edge deletions. A graph relation J≤GJ \le G on the same vertex type permits edge deletions and can represent vertex deletions by treating the deleted vertices as isolated.

Table 1 lists the selected correspondences. The Lean proof establishes the 4-colorability conclusion of Theorem 3.1 directly by finite-set induction using the low-degree vertex supplied by the cut argument. The library chromatic number takes values in the extended natural numbers. Its natural-valued girth is zero for an acyclic graph, whereas the written proof assigns infinite girth to forests. The formal proof uses the implication from library girth at least five to four-cycle-freeness. The statement about four-cycle-free subgraphs also covers forests. The final family is transported by ULift to the universe quantified over by the target.

Mathematical statementLean declaration
Lemma 2.3base_colorable_of_arc_colorable
Lemma 2.4arc_subgraph_colorable_bound
Lemma 3.2model_sizes_exist
Lemma 3.3, coloring conclusioncolorable_four_of_sparse_cuts
Lemma 3.4model_badSparse_probability_le
Lemma 3.5model_badColor_probability_le
Theorem 3.1, needed conclusionsmodel_base_exists
Theorem 1.1, family and coloringarc_counterexample_family
Corollary 1.2, pinned targettarget

Table 1. Selected correspondences with the submitted Lean file. Declaration names lie in namespace Bounty.

Pinned environment and scope of verification. The supplied checks use Lean 4.33.1 [4], mathlib revision 0df444a360ea, and Formal Conjectures task revision 8432eac99811. The unwrapped proof ends with the declaration below, where Not is written as Lean’s negation symbol.

theorem target : Not (fcTypeOfName% "Erdos108.erdos_108") := by
  exact counterexample_of_family counterexample_family

The task’s type extractor supplies the statement. The local axiom audit for Bounty.target reports exactly propext, Classical.choice, and Quot.sound. The pinned source edition supplies the accepted proof body, the task wrapper, and the local build log and digest [5]. Conjectures.io records production verification and public certification of the negative answer [6]. These records apply to the original target. The original manuscript [7] names two additional Lean declarations for the triangle-free strengthening. The source documentation records that those declarations are absent from the supplied proof [8].

Concluding remarks

The obstruction is uniform. The bound six does not depend on the chromatic number of the host graph. Hence the same family excludes a threshold for every girth parameter r≥5r \ge5 at chromatic parameter k=7k = 7. The argument does not establish whether six is the smallest possible uniform bound.

The sizes in (4)–(5) were chosen to simplify the proof and its formalization. They specify a finite construction, but are far too large to make enumeration of the required realizations practical. The conclusion is an existence theorem proved by the finite probability estimates above.

Acknowledgements and AI-use disclosure. This work was developed with substantial assistance from OpenAI ChatGPT/Codex, including mathematical exploration, the preparation and checking of estimates, construction and debugging of the Lean proofs, and drafting and typesetting of the manuscript. Jensen Kohlmeyer and Liam Kruer are responsible for the mathematical content and its presentation. The formal source and the verification record make the machine-checked claims inspectable.

References

  1. [1]T. F. Bloom, Erdős Problem #108, Erdős Problems.
  2. [2]Google DeepMind and contributors, Formal Conjectures, file FormalConjectures/ErdosProblems/108.lean, repository. The task revision is specified in Section 5.
  3. [3]B. Janzer, R. Steiner and B. Sudakov, Chromatic number and regular subgraphs, Bull. London Math. Soc. (2026), DOI, preprint arXiv:2410.02437.arxiv.org/abs/2410.02437
  4. [4]Lean community, The Lean 4 theorem prover, version 4.33.1.
  5. [5]Pinned original-source edition and verification report.
  6. [6]Conjectures.io, Erdős problem 108, production verification record.
  7. [7]J. Kohlmeyer and L. Kruer, Original arc-graph manuscript, September 15, 2026, linked from Justin Sun Prize submission JSP-000120.
  8. [8]Source notes on manuscript correspondence, pinned at the manuscript revision.

Paper details

vlnc:W_9ka3ag4w
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents