Erdős Problem #1022

Erdős Problem 1022

Statement and answer.

Can constants $c_t\to\infty$ guarantee property B for every finite family $\mathcal F$ of sets of size at least $t$, under the condition \[ |\{A\in\mathcal F:A\subseteq X\}|<c_t|X| \quad\text{for every nonempty }X? \] No. For each $t\geq2$ we construct a $t$-uniform family that is not two-colourable and satisfies the strict bound with $c_t=2$. Thus any constants having the asserted implication must be less than two, so cannot tend to infinity.

The nonempty qualification is essential: at $X=\varnothing$, the literal strict inequality would read $0<0$. It is also present in the formal statement linked in the discussion. The page's affirmative status heading is inconsistent with the negative mathematical answer explained in its editorial and comments. We prove the negative answer explicitly.

A finite construction in three layers.

Put $r=t-1\geq1$, and take a set $\Gamma$ of $3r$ vertices. For every ordered pair of disjoint $r$-subsets $A,B\subseteq\Gamma$, introduce a fresh vertex $v_{A,B}$ and the edges \[ A\cup\{v_{A,B}\},\qquad B\cup\{v_{A,B}\}. \] Let $V$ be the set of all these fresh vertices. For every $r$-subset $Q\subseteq\Gamma$ and $r$-subset $R\subseteq V$, introduce another fresh vertex $w_{Q,R}$ and the edges \[ Q\cup\{w_{Q,R}\},\qquad R\cup\{w_{Q,R}\}. \] Let $W$ be this third layer, and let $\mathcal F$ consist of precisely the displayed edges. All layers are disjoint, all edges have $r+1=t$ vertices, and each fresh vertex is the distinguished last vertex of exactly two edges. The use of ordered pairs causes no repeated edges, because different pairs have different fresh vertices and $A\cap B=\varnothing$.

Why two colours are impossible.

Suppose the vertices were coloured red and blue without a monochromatic edge. If $\Gamma$ had both an all-red $r$-set $A$ and an all-blue $r$-set $B$, then whichever colour $v_{A,B}$ received would complete a monochromatic edge. Thus one colour occurs fewer than $r$ times in $\Gamma$. Interchanging colours, there are at least $2r+1$ red vertices.

Choose $2r$ red vertices. Each of their ordered partitions into two $r$-sets $A,B$ forces $v_{A,B}$ to be blue. These vertices are distinct, and their number is $\binom{2r}{r}\geq r$. Choose an all-blue $r$-set $R\subseteq V$, and choose an all-red $r$-set $Q\subseteq\Gamma$. Now $w_{Q,R}$ again completes a monochromatic edge whichever colour it receives. This contradiction proves failure of property B.

The family actually has chromatic number exactly three: colour $\Gamma,V,W$ with three different colours. Every edge meets two different layers and so is nonmonochromatic.

The strict local density bound.

Charge each edge to its distinguished fresh vertex in $V$ or $W$. Every vertex receives at most two charges, and the charged vertex belongs to the edge. This initially gives $e_{\mathcal F}(X)\leq2|X|$. To obtain the strict inequality required in the question, order all vertices with $\Gamma$ first, $V$ next, and $W$ last, using arbitrary orders within layers.

For nonempty $X$, let $x$ be its earliest vertex. No edge contained in $X$ can be charged to $x$: a charged edge contains $r\geq1$ vertices from an earlier layer, and a vertex of $\Gamma$ receives no charges at all. Every other vertex of $X$ receives at most two charges. Hence \[ e_{\mathcal F}(X)\leq2(|X|-1)<2|X|. \tag{1} \] The same estimate holds if $X$ contains additional vertices outside the construction, by intersecting it with the vertex set (and treating the empty intersection separately). Thus $1$ verifies every nonempty set in the hypothesis.

Equivalently, deleting vertices in reverse layer order gives a degeneracy bound of two: each vertex, when deleted, is incident with at most its two own edges. The strict charge argument above directly checks the stated density condition and does not confuse that condition with an equivalent definition of degeneracy.

Conclusion and attribution.

For each $t\geq2$, this one family contradicts the proposed implication whenever $c_t\geq2$. Consequently a sequence of constants with that implication cannot tend to infinity.

The construction adapts KoishiChan's explicit example in the discussion, with the two sizes in the final step kept separate and the strict inequality checked: https://www.erdosproblems.com/forum/thread/1022. The prior general construction is D. R. Wood, Hypergraph Colouring and Degeneracy, https://arxiv.org/abs/1310.2972. Source statement: https://www.erdosproblems.com/1022, checked 24 September 2026. The proof here is elementary and self-contained; neither Wood's theorem nor a local Lean verification is assumed. No novelty is claimed.

Completion rate estimate: 100%.

Is there a constant $c_t$, where $c_t\to \infty$ as $t\to \infty$, such that if $\mathcal{F}$ is a finite family of finite sets, all of size at least $t$, and for every set $X$ there are $<c_t\lvert X\rvert$ many $A\in \mathcal{F}$ with $A\subseteq X$, then $\mathcal{F}$ has chromatic number $2$ (in other words, has property B)? Erdős originally conjectured, in this language, that $c_2=1$, which was proved by Lovász [Lo68]. References [Lo68] Lovász, L., On covering of graphs . Theory of Graphs (Proc. Colloq., Tihany, 1966) $1968$, 231-236.

Erdős Problem #1022 --- Solution Attempt

FORMAL RESTATEMENT. Fix an integer $t\ge 2$. Let $\mathcal{F}$ be a finite family of finite sets ("edges") and let \[ V := \bigcup_{A\in\mathcal{F}} A \] be the finite "vertex set". Assume $|A|\ge t$ for every $A\in\mathcal{F}$. For any subset $X\subseteq V$, define \[ \mathcal{F}[X] := \{A\in\mathcal{F}: A\subseteq X\},\qquad e(X):=|\mathcal{F}[X]|. \] The hypothesis is that for every $X\subseteq V$ we have \[ e(X) < c_t\,|X|. \] The conclusion "$\mathcal{F}$ has chromatic number $2$ / has property B" means: there exists a map $\chi:V\to\{\text{red},\text{blue}\}$ such that for every $A\in\mathcal{F}$, the restriction $\chi|_A$ is not constant.

The question: do there exist constants $c_t$ (depending only on $t$) with $c_t\to\infty$ as $t\to\infty$ such that the above implication holds for every such finite $\mathcal{F}$?

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records that for $t=2$ one can take $c_2=1$ (Lovász [Lo68]). I do not use any external results beyond what is explicitly in the problem file.

ATTACK PLAN. Proof track: try to deduce 2-colourability from the local bound $e(X)<c_t|X|$ via an inductive deletion argument (looking for a low "degree" vertex), or via a probabilistic colouring + Local Lemma style condition (but any such argument must exploit the specific "subsets $X$" constraint).

Disproof track: search for explicit non-2-colourable $t$-uniform (or $\ge t$-uniform) hypergraphs where every induced subhypergraph has at most $O(|X|)$ edges, with the constant of proportionality as large as possible. Projective-plane type designs are natural candidates.

I follow the disproof/proof tracks only far enough to obtain rigorous partial results and explicit obstructions.

WORK.

Lemma 1 (A $c_t=1$ inductive sufficient condition for property B). Let $\mathcal{F}$ be a finite family of subsets of a finite set $V$, with $|A|\ge 2$ for all $A\in\mathcal{F}$. Assume that for every nonempty $X\subseteq V$, \[ |\{A\in\mathcal{F}: A\subseteq X\}| \le |X|-1. \] Then $\mathcal{F}$ has property B.

Proof. We prove by induction on $n:=|V|$.

Base cases: $n\le 1$ are trivial because there are no edges of size $\ge 2$.

Inductive step: assume $n\ge 2$ and the statement holds for all smaller $|V|$. For each vertex $v\in V$, define its hyperedge-degree \[ d(v):=|\{A\in\mathcal{F}: v\in A\}|. \] Suppose for contradiction that $d(v)\ge 2$ for every $v\in V$. Then \[ \sum_{v\in V} d(v) \ge 2|V|=2n. \] On the other hand, \[ \sum_{v\in V} d(v) = \sum_{A\in\mathcal{F}} |A| \ge 2|\mathcal{F}|, \] because each edge has size at least $2$. Combining gives $2|\mathcal{F}|\ge 2n$, i.e. $|\mathcal{F}|\ge n$. But applying the hypothesis to $X=V$ yields $|\mathcal{F}|\le |V|-1=n-1$, a contradiction. Therefore there exists a vertex $v\in V$ with $d(v)\le 1$.

Let $V':=V\setminus\{v\}$ and let $\mathcal{F}':=\{A\in\mathcal{F}: v\notin A\}$. For any nonempty $X\subseteq V'$, the sets in $\mathcal{F}'$ contained in $X$ are exactly the sets in $\mathcal{F}$ contained in $X$, hence \[ |\{A\in\mathcal{F}':A\subseteq X\}| \le |X|-1. \] Thus $\mathcal{F}'$ satisfies the same hypothesis on the smaller vertex set $V'$. By the induction hypothesis, there exists a 2-colouring $\chi':V'\to\{\text{red},\text{blue}\}$ such that no edge of $\mathcal{F}'$ is monochromatic.

We extend $\chi'$ to $V$. If $d(v)=0$, then $v$ lies in no edge, so assigning either colour to $v$ preserves property B. If $d(v)=1$, let $A\in\mathcal{F}$ be the unique edge containing $v$. Then all other edges are in $\mathcal{F}'$ and are already non-monochromatic. If $\chi'$ is not constant on $A\setminus\{v\}$, again either colour on $v$ makes $A$ non-monochromatic. If instead all vertices of $A\setminus\{v\}$ have the same colour under $\chi'$, assign $v$ the opposite colour. Then $A$ is not monochromatic. In all cases we obtain a 2-colouring of $V$ witnessing property B for $\mathcal{F}$. $\square$

Comment. Lemma 1 gives a complete proof that the implication in the problem holds with $c_t=1$ for every $t\ge 2$. However, it does not address the requirement $c_t\to\infty$.

Lemma 2 (A concrete obstruction at $t=3$: the Fano plane forces $c_3\le 1$). Let $V=\{1,2,3,4,5,6,7\}$ and let $\mathcal{F}$ be the $7$ triples \[ \{1,2,3\},\ \{1,4,5\},\ \{1,6,7\},\ \{2,4,6\},\ \{2,5,7\},\ \{3,4,7\},\ \{3,5,6\}. \] Then:

1. (a) For every subset $X\subseteq V$, one has $|\{A\in\mathcal{F}:A\subseteq X\}|\le |X|$.
2. (b) $\mathcal{F}$ does not have property B (i.e. it is not 2-colourable).

Consequently, for $t=3$ the statement of the problem cannot hold for any constant $c_3>1$.

Proof of (a). For $v\in V$, let $d(v)$ be the number of triples in $\mathcal{F}$ containing $v$. From the explicit list, each vertex appears in exactly $3$ triples (one checks this by inspection of the seven triples). Fix any $X\subseteq V$ and let $e(X)$ denote the number of triples contained in $X$. Counting incidences between vertices of $X$ and triples contained in $X$ gives \[ 3e(X) = \sum_{A\in\mathcal{F}[X]} |A| = \sum_{A\in\mathcal{F}[X]} 3. \] On the other hand, each $v\in X$ belongs to at most $3$ triples in total, hence also to at most $3$ triples contained in $X$, so the number of such incidences is at most $\sum_{v\in X} 3 = 3|X|$. Therefore $3e(X)\le 3|X|$, i.e. $e(X)\le |X|$.

Proof of (b). Assume for contradiction that there is a 2-colouring of $V$ into red and blue such that no triple in $\mathcal{F}$ is monochromatic. Let $r$ be the number of red vertices (so $0\le r\le 7$). Under the assumption "no monochromatic triple", every triple has type $(2\text{ red},1\text{ blue})$ or $(1\text{ red},2\text{ blue})$. Let $x$ be the number of triples with exactly $2$ red vertices.

First count red incidences with triples. Each red vertex lies in exactly $3$ triples, so the total number of (red vertex, triple) incidences equals $3r$. On the other hand, each of the $x$ triples of type $(2R,1B)$ contributes $2$ red incidences, and each of the $7-x$ remaining triples contributes $1$ red incidence. Thus \[ 3r = 2x + 1\cdot(7-x) = x+7, \] so \[ x = 3r-7. \tag{1} \]

Next count red pairs. There are $\binom{7}{2}=21$ unordered pairs of vertices, and each triple contains $\binom{3}{2}=3$ pairs. Since $\mathcal{F}$ has $7$ triples, the total number of pair-occurrences across all triples is $7\cdot 3=21$. A direct check from the explicit list shows that no two distinct triples share two vertices (equivalently: the intersection of any two distinct triples has size at most $1$). Therefore all $21$ pair-occurrences are distinct, so every unordered pair of vertices lies in exactly one triple of $\mathcal{F}$.

Consider any red pair $\{u,v\}$. The unique triple containing this pair cannot be monochromatic red, so its third vertex must be blue. Hence the unique triple containing $\{u,v\}$ is of type $(2R,1B)$. Conversely, each triple of type $(2R,1B)$ contains exactly one red pair. Thus the number of red pairs equals $x$. But the number of red pairs is also $\binom{r}{2}$. Therefore \[ \binom{r}{2} = x. \tag{2} \] Combining $1$ and $2$ gives \[ \frac{r(r-1)}{2} = 3r-7 \quad\Longrightarrow\quad r^2-7r+14=0, \] whose discriminant is $49-56=-7<0$, impossible for an integer $r$. This contradiction shows that no such 2-colouring exists; hence $\mathcal{F}$ is not property B. $\square$

FAST REALITY CHECK (small cases / computation).

• For $t=2$ and $c_2=1$, the condition becomes: for every $X\subseteq V$, the induced subgraph on $X$ has $<|X|$ edges. I exhaustively checked all labelled graphs on $n\le 6$ vertices; every graph satisfying this condition was bipartite. Counts: for $n=2,3,4,5,6$ the numbers of graphs satisfying the condition are $2,7,38,291,2932$, and all are bipartite.
• For the Fano plane family in Lemma 2, I exhaustively checked all $2^7$ vertex 2-colourings and found none avoids a monochromatic triple. I also checked for every $X\subseteq V$ that $e(X)\le |X|$.

VERIFICATION.

• Lemma 1: the only subtle point is that deleting $v$ and restricting to edges not containing $v$ preserves the hypothesis for all $X\subseteq V'$. This holds because containment $A\subseteq X$ in $V'$ is the same statement in the original hypergraph, and edges containing $v$ cannot be contained in $X\subseteq V'$.
• Lemma 2(b): the "pair lies in exactly one triple" step is justified by (i) total pair-occurrences $=21$ and (ii) no repeated pair-occurrence, i.e. no two triples share two vertices, which can be verified directly from the explicit list (only $\binom{7}{2}=21$ triple-pairs to check).
• The obstruction conclusion: since $e(V)=7$ and $|V|=7$, for any $c_3>1$ we have $e(V)=7 < c_3\cdot 7$ and similarly $e(X)\le |X|<c_3|X|$ for all nonempty $X$. Thus the hypothesis of the problem holds for that $c_3$, while the conclusion fails.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. The implication holds with the fixed constant $c_t=1$ for every $t\ge 2$ (Lemma 1). Also, for $t=3$ any choice $c_3>1$ fails (Lemma 2).

(ii) First gap (crisp). Prove or disprove: there exists a function $t\mapsto c_t$ with $c_t\to\infty$ such that every finite hypergraph with all edges of size $\ge t$ and satisfying $e(X)<c_t|X|$ for all $X\subseteq V$ is 2-colourable.

(iii) Top 3 next moves. 1. Try to construct, for each large $t$, an explicit non-2-colourable $t$-uniform hypergraph with $e(X)\le C|X|$ for all $X$ where $C$ is as large as possible; determine whether $C$ can grow with $t$. 2. Attempt a proof scheme: show the condition $e(X)<c|X|$ forces a vertex of small degree (as in Lemma 1) when $c$ is large relative to $t$, and then extend the deletion argument to $t$-uniform constraints. 3. Try probabilistic colouring + a dependency graph that uses the stronger hypothesis "for all $X$" rather than only global $|\mathcal{F}|$; explicitly target a Local Lemma criterion that would allow $c_t$ to grow with $t$.

(iv) What a minimal counterexample would likely look like. A non-2-colourable $t$-uniform (or $\ge t$-uniform) hypergraph that is very "linear" (few overlaps), with induced subhypergraphs having edge-count comparable to $|X|$ (to satisfy the local sparsity), i.e. a design-like structure where every vertex has bounded degree but the hypergraph still forces a monochromatic edge in every 2-colouring.