Mantel’s Theorem for Random Graphs
[May, 2012]
If we let b(G) be the size of the largest bipartite subgraph of a graph G and t(G) be the size of the largest triangle-free subgraph, then t(G) is at least as large as b(G) because bipartite graphs are triangle free. An open question from about 20 years ago asked: for what p is it likely that t(G)=b(G) for a random graph G(n,p), where n is the number of vertices and p is the probably with which each edge appears? DeMarco and Kahn settled this question by showing that if p > Cn1/2log1/2(n) for a suitable constant C, then with probability going to one as n goes to infinity, t(G)=b(G). This result is tight up to the value of constant C.
For roughly the past two decades, demonstrating analogues of extremal results for random structures has been a very active area of research. DeMarco and Kahn’s result is one such analogue, but several celebrated extremal results also have natural analogues in a random setting. For example, random analogues of Ramsey’s Theorem, Szemeredi’s Theorem on arithmetic progressions, and Turan’s Theorem on the density of graphs without a k-sized clique have all been demonstrated in the past twenty years.
This new result
was part of DeMarco’s PhD dissertation on the mathematical
structure of random graphs which he successfully defended in May
2012. DeMarco received a 3-year fellowship through
DIMACS/CCICADA to support his graduate studies in mathematics.
The fellowship was funded by a grant to DIMACS/CCICADA from the
Department of Homeland Security.