University of Minnesota Combinatorics Seminar
Friday, October 26, 2012
3:35pm in 570 Vincent Hall



Extremal F5-free subgraphs of the random hypergraph

Jane Butterfield

University of Minnesota


Abstract

No k-partite graph contains any graph whose chromatic number is k + 1. It is natural to then ask: if H has chromatic number k + 1, is the largest graph that does not contain H necessarily k-partite? This question has been asked of both graphs and hypergraphs. Babai, Simonovits, and Spencer considered a "sparse" version of this question: is the largest triangle-free subgraph of the random graph necessarily bipartite? DeMarco and Khan settled this question very recently. We consider a 3-uniform hypergraph version of this question, replacing triangles with the hypergraph F5. We prove that for sufficiently large p it is almost surely the case that any largest F5-free subgraph of the random hypergraph G3(n,p) is tripartite.