Disjoint subgraphs of large maximum degree (Q1598819)

The authors study the minimum size \(b(n,m)\) of a graph \(G=(V,E)\) such that for every partition \(V=A\cup B\) either \(\Delta(G[A])\geq n\) or \(\Delta(G[B])\geq m\) and the minimum size \(q(n,j,l)\) of a graph \(G=(V,E)\) having \(n+j+l\) vertices such that \(\Delta(G[A])\geq n\) for every set \(A\subseteq V\) with \(|A|=n+j\). Erdős conjectured \(b(n,n)={2n+1\choose 2}-{n\choose 2}\). As a first result the authors give a probabilistic construction of a counterexample to this conjecture whose order is smaller than the order of the previously known counterexamples. They prove \(b(n,m)=2nm-m^2+O(\sqrt{m})n\) for \(n\geq m\geq 1\), \(b(n,1)=4n-2\) for \(n\geq 7\) and \(6n-110\leq b(n,2)\leq 6n-1\) for \(n\geq 2\). Furthermore, they prove \[ q(n,j,l)=(1+o(1))(l+1)n\left( 1+\frac{l}{2n+2j}\right)\quad \text{for}\quad l=o(n(n+j)/\log(n)) \] which disproves a conjectures of Erdős, Reid, Schelp and Staton. Some more related results are presented. The proofs rely on the probabilistic method and explicit constructions.