The fine structure of octahedron-free graphs (Q631642)

This paper is one of a series of papers in which the authors investigate a classic problem in extremal graph theory: Given a family \(L\) of `forbidden graphs', determine the maximum number of edges that a graph can have on \(n\) vertices, not containing any member of \(L\) as a (not necessarily induced) subgraph. More precisely, the authors are seeking a characterization of the set of \(L\)-free graphs, and to establish a relationship between the set of \(L\)-free graphs and the subgraphs of the \(L\)-extremal graphs. This continues the line of research started by \textit{P. Erdös, P. Frankl} and \textit{V. Rödl} [``The asymptotic number of graphs not containing a fixed subgraph, and a problem for hypergraphs having no exponent'', Graphs Comb. 2, 113--121 (1986; Zbl 0593.05038)]. In this particular chapter of the series, the authors concentrate on the octahedron as forbidden graph, and they prove several results about the typical structure of octahedron-free graphs, such as: 1. The vertex set of almost every octahedron-free graph can be partitioned into two classes of almost equal sizes, \(U_1\) and \(U_2\), where the graph spanned by \(U_1\) is \(C_4\)-free, and the graph spanned by \(U_2\) is \(P_3\)-free. 2. Similar assertions hold when \(L\) is the family of all graphs with 6 vertices and 12 edges, so that in some sense, the octahedron is a representative of that family of graphs. The style of the paper is quite technical, and it is worth noting that the authors have kept the same terminology and notation throughout the whole series.