Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let . Is it true that
where is the graph on vertices , where is adjacent to all and each pair of is adjacent to a unique .
Let . Is it true that
where is the graph on vertices , where is adjacent to all and each pair of is adjacent to a unique , a different for each pair, and has no other edges.
Source: erdosproblems.com/926
An accepted solution exists. The statement is true.
The site labels the problem PROVED. The status-defining source is Theorem 1.4 of Füredi ([Fu91], Combinatorica 11 (1991), 75--79, refereed), which bounds by an explicit multiple of for every and ; at the graph is the problem's of the precise Statement. The claim pages are Füredi (accepted on the refereed publication and the acceptance of the site's curator, Thomas Bloom; the site's label is its discussion link) and Alon, Krivelevich and Sudakov (Theorem 6.1 of [AKS03], Combin. Probab. Comput. 12 (2003), refereed: a second proof with the sharper bound , accepted on the refereed publication alone, since the site's entry thanks Noga Alon and the curator's credit is therefore not listed as independent review). The frontmatter is derived from them.
The site writes "each pair of is adjacent to a unique ", an index that does not say on its face whether different pairs may share a . The sources fix one vertex for each pair. Erdős's source [Er71] (item 15, pp. 103--104) defines the graph, there called , as a vertex joined to with each pair of the 's joined to its own vertex (see the source card). Füredi's paper on this question [Fu91] (printed p. 76) defines the same graph , the lowest three levels of the Boolean lattice, with one vertex for each pair joined to exactly and , and the site's commentary credits that theorem with the answer. The site's own vertex list, with vertices , has one for each pair. The precise Statement takes this reading: the vertex of the pair , with edges , and and no others. The formal-conjectures statement (see Formalization) uses the same graph.