The local density of triangle-free graphs (Q1382812): Difference between revisions

The objective of the paper is to determine for real numbers \(a\) \((0\leq a\leq 1)\) the smallest real number \(b(a)\) with the property that every triangle-free graph of order \(n\) has subsets of \(\lfloor an\rfloor\) vertices which span at most \(b(a)n^2\) edges. It is shown that the minimum number of edges which need to be deleted to make a regular graph of order \(n\) bipartite is at least \((c_1+ c_n)n/4\), where \(c_1\geq c_2\geq \cdots\geq c_n\) are the eigenvalues of the adjacency matrix of the graph. Finally, a conjecture about the spectrum of regular triangle-free graphs is raised.