The largest subgraph without a forbidden induced subgraph (Q6872192)

A property of graphs is hereditary if it is closed under taking induced subgraphs. Let \(G\) be a graph with \(n\) vertices such that the edge density between any pair of subsets of vertices of size at least \(t\) is at most \(1-c\), for some \(t\) and \(c> 0\). The paper considers the problem of finding the largest number of edges in a subgraph of \(G\) which does not contain a fixed bipartite graph \(H\) as an induced subgraph. The authors determine the answer up to a constant factor with respect to \(n\) and \(t\), for certain bipartite \(H\) and for either a dense random graph or a Paley graph with a square number of vertices. As an application, the result determines the largest subgraph with a hereditary property which misses a bipartite graph, and determine up to a constant factor the largest number of edges in a string subgraph of \(G\).