Large triangle-free subgraphs in graphs without \(K_ 4\) (Q1078195): Difference between revisions

It is shown that for arbitrary positive \(\epsilon\) there exists a graph without \(K_ 4\) and with the property that all its subgraphs containing more than \(1/2+\epsilon\) portion of its edges contain a triangle. This solves a problem of Erdős and Nešetřil. On the other hand it is proved that such graphs have necessarily low edge density. The authors show that random graphs behave in some respect as sparse complete graphs, further they prove the existence of a graph on less than \(10^{12}\) vertices, without \(K_ 4\) and which is edge-Ramsey for triangles.