Problem 1078

Let $G$ be an $r$ -partite graph with $n$ vertices in each part. If $G$ has minimum degree $\geq (r-\frac{3}{2}-o(1))n$ then $G$ must contain a $K_r$ .

Source: erdosproblems.com/1078

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, the site's label. The site's status-defining source is Haxell [Ha01] (Combin. Probab. Comput. 10 (2001), 345--347; refereed), not held: its abstract, on the publisher's article page, states a list-coloring theorem (lists of size $2k$ , each color on the lists of at most $k$ neighbors of any vertex, a proper coloring from the lists exists, "a weak version of a conjecture of Reed"), and the paper of Haxell and Szabó attests its bearing on this problem: "This was improved to $\Delta_r\ge1/2$ in [9], which settled the conjecture of [7] and established $\mu=1/2$ " ([HaSz06], p. 2; [9] is [Ha01] and [7] is [BES75b]). The stronger result is Theorem 1.1 (Haxell and Szabó 2006) of [HaSz06] (Combin. Probab. Comput. 15 (2006), 193--211; refereed; paged by the authors' preprint): for every integer $n\ge1$ and odd $r\ge2$ , $\Delta(r,n)=\Delta(r-1,n)=\lceil\frac{(r-1)n}{2(r-2)}\rceil$ , where $\Delta(r,n)$ is the largest integer such that every $r$ -partite graph with parts of size $n$ and maximum degree less than $\Delta(r,n)$ has an independent transversal. By complementation, an authored deduction written out in the Current assessment,

f_r(n)=(r-1)n-\Bigl\lceil\frac{sn}{2s-1}\Bigr\rceil,\qquad s=\lfloor r/2\rfloor,

for every $r\ge3$ and $n\ge1$ : every $G_r(n)$ with minimum degree above this value contains a $K_r$ , and some $G_r(n)$ with exactly this minimum degree does not, which is the sharp threshold the site prints. Since $f_r(n)<(r-\frac32)n$ for every $r\ge3$ , minimum degree at least $(r-\frac32)n$ forces a $K_r$ , and $c_r=r-\frac32-\frac1{2(r-2)}$ for odd $r$ and $r-\frac32-\frac1{2(r-1)}$ for even $r$ , so that $\lim_{r\to\infty}(c_r-r+2)=\frac12$ , the 1975 conjecture. The claim pages record Haxell's note (Haxell 2001) and the Haxell--Szabó theorem (Haxell and Szabó 2006), both refereed and both named by the site.

BES75b: Bollobás, B., Erdős, P. and Szemerédi, E., On complete subgraphs of $r$ -chromatic graphs. Discrete Math. 13 (1975), no. 2, 97--107, doi:10.1016/0012-365X(75)90011-4 (Crossref record read; received 7 November 1974). The abstract, p. 97; the Oxford conjecture, $f_r(n)$ , the bounds on $c_r$ and the conjecture, p. 98; the constructions $F_4(n)$ and $F_r(n)$ , pp. 104--105; Theorem 3.1 and Corollary 3.2, p. 105; Theorem 3.3, p. 106. Library home: Bollobás and Szemerédi 1975 (the Rényi archive's scan); paged at Bollobás and Szemerédi 1975, Bounds on c_r (p. 98) and Bollobás and Szemerédi 1975, Conjecture (p. 98).
Ha01: Haxell, P. E., A note on vertex list colouring. Combin. Probab. Comput. 10 (2001), no. 4, 345--347, doi:10.1017/S0963548301004758 (Crossref record read; published July 2001, online 2 October 2001 per the publisher's page). Not held: the DOI resolves to the publisher's article page, which offers the article behind access and shows its abstract; no open copy was located.
HaSz06: Haxell, P. and Szabó, T., Odd independent transversals are odd. Combin. Probab. Comput. 15 (2006), no. 1--2, 193--211, doi:10.1017/S0963548305007157 (Crossref record read). Theorem 1.1 and the introduction's history, pp. 1--2 of the authors' preprint; Theorem 4.1, p. 14. Library home: Haxell and Szabó 2006 (the authors' preprint, 20 pages, without the journal pagination); paged at Haxell and Szabó 2006, Theorem 1.1 (p. 2).
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; the opening of Chapter 4, printed p. 12. Library home: Erdős 1975; the passage is paged at Erdős 1975, Conjecture (Chapter 4, printed p. 12 = PDF p. 10).
Er72: Erdős, P., Problem 2, in: Combinatorics (D. J. A. Welsh and D. R. Woodall, eds.), The Institute of Mathematics and its Applications (1972), 353--354; the Oxford 1972 conjecture as [BES75b] cites it (its [7]). Not held.
Ji92: Jin, G., Complete subgraphs of $r$ -partite graphs. Combin. Probab. Comput. 1 (1992), no. 3, 241--250. Not held; cited by [HaSz06] (its [11]) for $\Delta_4=\Delta_5=2/3$ .
SzTa: Szabó, T. and Tardos, G., Extremal problems for transversals in graphs with bounded degree. Combinatorica, "to appear" as [HaSz06] cites it (its [14]). Not held; the construction for an even number of parts.

Problem 1078

Status

Proof claims

Discussion