Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. The least number of edges of a 44-uniform hypergraph that does not have property B, that is, that is not 2-colorable, is 2323: in the notation of Problem 901, m(4)=23m(4)=23. The paper's abstract records the earlier range 21≤m(4)≤2321\le m(4)\le23 and determines the value by an exhaustive computer search for 44-uniform hypergraphs with fewer than 2323 edges and no proper 2-coloring, which finds none.

Covers. The instance n=4n=4 of the question, the exact value m(4)=23m(4)=23, which the site lists without a source. The values m(2)=3m(2)=3 and m(3)=7m(3)=7 are recorded in Erdős's 1963 paper. No value m(n)m(n) with n≥5n\ge5 is known, and the order of m(n)m(n) stays open.

Depends on. No page of this wiki.

Acceptance. P. R. J. Östergård, On the minimum size of 4-uniform hypergraphs without property B, Discrete Appl. Math. 163 (2014), part 2, 199--204, a refereed journal (refereed); the record dates the issue to January 2014 without a day, so the page is dated to the first day of that month. The site lists m(4)=23m(4)=23 in the problem's commentary without crediting a source, and labels the problem OPEN, so the commentary is not acceptance of this partial claim.