Erdős problem 1022 · problems.science

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)?

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1022.lean

Retained formal statement3 of 3

This is false, and $c_t<2$ for all $t$ : a counterexample is provided by Wood [Wo13b], who constructs, for any $r\geq 2$ , a triangle-free $2$ -degenerate $r$ -uniform hypergraph with chromatic number $3$ . A similar counterexample was found independently by KoishiChan in the comments.

FormalConjectures/ErdosProblems/1022.leanErdos1022.erdos_1022.variants.lt_two1 lineExact file

1True ↔ ∀ (t : ℕ) (c : ℝ), Erdos1022.SparseImpliesPropertyB t c → c < 2

SolvedStatement only, no proof

Sources

Search problems.science