This page was last edited 25 January 2026. View history
| Likes this problem | None |
| Interested in collaborating | None |
| Currently working on this problem | None |
| This problem looks difficult | None |
| This problem looks tractable | None |
| The results on this problem could be formalisable | None |
| I am working on formalising the results on this problem | None |
Hi Bloom, I think the problem is actually already solved by David R. Wood in https://arxiv.org/pdf/1310.2972. The condition Erdos mentioned is equivalent to c_t - degeneracy, so the result follows from Wood's main theorem.
Thanks! I don't think the condition here is equivalent to $c_t$-degeneracy, it's a weaker condition (consider the family of $\{1,\ldots,n\}\backslash \{i\}$ for $1\leq i\leq n$, which satisfies this condition for any $c>1$, but every vertex has degree $n-1$). But $<c_t$-degenerate does imply the given condition, so certainly Wood's example still works here.
This problem seems to admit a trivial counterexample showing that $c_t < 2$ for every $t$. I use $F$ as the hypergraph, since $\mathcal{F}$ does not render on many computers.
Let $\Gamma$ be a vertex set of size $3t$. For each pair of subsets $A, B \subset \Gamma$ of size $t$, add a new vertex $v_{A, B}$ and sets $A \cup \{v_{A, B}\}$ and $B \cup \{v_{A, B}\}$ to $F$. Let $V$ denote the set of $v_{A, B}$'s. Furthermore, for any $t$ element subset $Q$ of $\Gamma$ and $t$ element subset $R$ of $V$, add a new vertex $w_{Q, R}$ and sets $Q \cup \{w_{Q, R}\}$ and $R \cup \{w_{Q, R}\}$ to $F$. Thus, $X$ consists of $\Gamma$, $V$, and the vertices $w_{Q, R}$.
Clearly, $F$ is $(t + 1)$-uniform. We now claim that $F$ cannot be two-chromatic. Suppose the contrary and study a blue-red-coloring of $F$. If $\Gamma$ has $t$ red vertices $A$ and $t$ blue vertices $B$, then at least one of $A \cup \{v_{A, B}\}$ and $B \cup \{v_{A, B}\}$ is monochromatic, contradiction. Otherwise, $\Gamma$ contains at least $2t$ vertices of the same color, say red. Let $Q$ denote these red vertices. For any partition $Q = A \sqcup B$ into two sets of size $t$, $v_{A, B}$ must be blue. Hence $V$ contains at least $\binom{2t}{t} \geq t$ blue vertices. Letting $R$ be any $t$ blue vertices in $V$, at least one of $Q \cup \{w_{Q, R}\}$ and $R \cup \{w_{Q, R}\}$ must be monochromatic, contradiction.
Finally, there exists a $2$-to-$1$ matching from $F$ to $X$: let $\phi: F\to X$ map $A \cup \{v_{A, B}\}$ and $B \cup \{v_{A, B}\}$ to $v_{A, B}$, and $Q \cup \{w_{Q, R}\}$ and $R \cup \{w_{Q, R}\}$ to $w_{Q, R}$. Then each vertex of $X$ has at most $2$ pre-images. For each $Y \subset X$, we have
$$\{S \in F: S \subset Y\} \subset \phi^{-1}(Y)$$
thus $|\{S \in F: S \subset Y\}| \leq | \phi^{-1}(Y)| \leq 2|Y|$, as desired.
The argument looks essentially correct to me (I also ran it through ChatGPT Pro, who only made some minor corrections, for instance that one should write $c_t \leq 2$ rather than $c_t < 2$). This also looks within range of being autoformalizable in Lean.
However, something is strange with the literature. The paper [Lo68] cited in the Erdos paper is about an unrelated problem. Erdos also cites a more promisingly titled paper of Lovasz, but the paper is mysteriously unavailable on the Springer site. I can see the first two pages of it at this alternate location, but again this doesn't quite seem to address the claimed problem. I looked at followup papers that cited either of these two papers, and while there is quite a bit of work on chromatic numbers of hypergraphs, I could not find a specific reference.
Deep Research tools failed quite badly in this case. Both ChatGPT Deep Research and Gemini Deep Research were wildly confused about different notions of hypergraph densities etc. and their reports are a incoherent mess of inaccurate statements (but presented in the usual confident-sounding LLM style, unfortunately).
A more manual literature search, or a consultation with an expert in the field, may be needed here to determine if this problem has been considered before in the literature, or if there is a potential misstatement by Erdos.
Hmm. Certainly it looks like the second Lovasz paper (also from 1968) is the relevant one. I could download it from Springer no problems, perhaps try again?
I believe that reference of Lovasz Erdős is using to refer to the other result mentioned in [Er71], the generalisation of Brooks' theorem, namely that if $\lvert A\rvert =r>2$ for all $A\in \mathcal{F}$ and the system is $k$-chromatic and does not contain all $r$-tuples of a set of $(k-1)(r-1)+1$ elements then there are $k$ many $A$ any two of which intersect in the same element. This is indeed a theorem proved in the second Lovasz paper.
I could not see anything in this paper directly relevant to the problem at hand; it may be that this was proved by Lovasz just in personal communication to Erdős, and never published.
I agree that some input from an expert on hypergraphs would be helpful here, perhaps there is some similar well-known and non-trivial problem that was intended here.
EDIT: For convience, I copy below the exact wording used by Erdős in [Er71]: "Probably the following result holds: there is a constant $c_t$, $c_t\to \infty$ as $t\to\infty$, so that if $\{A_l\}$ is a set-system, $\lvert A_l\rvert>t$, and for every $S_1\subset S$ there are fewer than $c_t\lvert S_1\rvert$ $A$'s contained in $S_1$, then the system has chromatic number $2$."
(He had earlier defined $\cup_l A_l=S$.) I believe what I have written in the problem statement is an accurate rephrasing of this.
In any case, the claim $c_2 = 1$ is easy (and was established in the aforementioned Gemini report, amidst a bunch of nonsense). Firstly, the example of an $n$-cycle for large odd $n$, which is not $2$-colorable but has at most $k$ edges in any $k$-element subset, shows that $c_2$ cannot exceed $1$. Now suppose that ${\mathcal F}$ obeys the hypotheses with $t=2$ and $c_2=1$. Then there can be no singleton or empty edges, and no loops, so the hypergraph is a graph tree, thus 2-colorable.
Given how simple the $c_2=1$ argument is, perhaps the most plausible explanation is that Erdos casually asked this question in some private context, Laci quickly responded with the easy $c_2=1$ argument, and Erdos then posed the higher $t$ problem without thinking too hard about it. It would be good to double check with a hypergraph expert, but I could not find any reference in the hypergraph coloring literature referencing a quantity like $c_t$ (a lot of work instead goes into questions relating to max degree etc., as this is relevant to apply the Lovasz local lemma, or the fewest edges needed in a t-uniform hypergraph to destroy 2-colorability).
I was led here because the Github repo marks this mysteriously with "literature review sought".
I agree with this interpretation.
In [Er71], in section 17, there are two separate statements containing "Lovasz proved":
1) "I conjectured and Lovasz proved that if $|A_i|\ge 2$ and for every $S_1 < S$ there are fewer than $S_1$ $A$'s contained in $S_1$ then the chromatic number of the system is $2$."
2) "Lovasz proved that if $|A_\ell| = r > 2$ and the set system is $k$-chromatic and does not contain all the $r$-tuples of a set of $(k-1)(r-1)+1$ elements, then there are $k$ $A$'s any two of which intersect in the same element. This is a generalization of a well-known theorem of Brooks."
The [Lo68] paper titled "On covering of graphs" appears unrelated to either problem. Meanwhile, the other [Lo68] paper titled "On chromatic number of finite set-systems" seems to be related to the second problem but not the first problem.
Since we are dealing with the first problem, to prevent confusion, it seems best to remove the [Lo68] reference from the problem description?
Credit: ChatGPT.
This proof has been formalized in Lean by Aristotle using (the negation of) the statement below. Type-check it online!
import Mathlib
abbrev Hypergraph (α : Type*) [DecidableEq α] := Finset (Finset α)
def TwoColorable {α : Type*} [DecidableEq α] (F : Hypergraph α) : Prop :=
∃ (c : α → Bool), ∀ A ∈ F, ∃ x y, x ∈ A ∧ y ∈ A ∧ c x ≠ c y
def erdos_1022 : Prop :=
∃ c : ℕ → ℝ, Filter.Tendsto c Filter.atTop Filter.atTop ∧
∀ t, ∀ {α : Type*} [DecidableEq α] (F : Hypergraph α),
(∀ A ∈ F, A.card ≥ t) →
(∀ X : Finset α, X.Nonempty → (F.filter (λ A => A ⊆ X)).card < c t * (X.card : ℝ)) →
TwoColorable F
I'll mark this for now under Section 2(b) of the wiki as a formalization of the "full solution" by KoishiChan, but this is provisional in case we do find an alternative formulation of the problem that replaces the current one. (Still waiting for a hypergraph expert to weigh in, I guess.)
On a related note, the page by Mehmet Mars Seven has ChatGPT Pro 5.2 proving that $c_3\le 2$ with the explicit example of the Fano plane.
Revisiting this now, I think I'll mark this as solved (by KoishiChan), since this answers the question as I understand it. If any expert later has a better interpretation of this problem, we can revisit this.
Log in to add a comment.
