Degree sequences of \(F\)-free graphs (Q2583671): Difference between revisions

The Erdős-Stone theorem states that, for an arbitrary graph \(F\) with chromatic number \(\chi(F)=r+1\), it holds that \[ \text{Max}\bigl\{e (G):\nu(G)=n,\;F\subseteq G\}=t_r(n)+o(n^2)\geq(1-1/r)n(n-1)/2, \] where \(t_r(n)\) is the number of edges of the Turin graph \(T_r(n)\), namely the complete \(r\)-partite graph on \(n\) vertices with parts as equal as possible. In other words, for every \(F\)-free graph \(G\) of order \(n\), there exists an \(r\)-partite graph \(H=T_r(n)\) with almost as many edges as \(G\). In the present paper, the authors consider the question whether analogous statements are true if one compares the degree sequences instead of total number of edges. They prove the following main theorem: Let \(F\) be a fixed non-empty graph of chromatic number \(\chi(F)=r+1\). For any \(\varepsilon >0\) and large \(n\geq n_0(\varepsilon,F)\) the degree sequence \(g_1\geq\cdots\geq g_n\) of any \(F\)-free graph \(G\) is \((\varepsilon n,\varepsilon n)\)-dominated by the degree sequence of some \(r\)-partite graph \(H\) of order \(n\). Two proofs of the main theorem are presented allowing for some technical improvements.