Discrete Geometric Structure Seminar
A new basic question about triangle-free graphs
Ross Kang (RU Nijmegen)
2018/10/18 (Thu) 10:30-12:00 (Rm 3-413)
Triangle-free graphs, that is, graphs for which no neighbourhood contains any edges, are of fundamental importance in discrete mathematics, as evidenced by a number of classic results, e.g. of Mantel (1907), Blanche Descartes (1948), Ajtai, Komlós and Szemerédi (1980). These are defined by a simple local structural criterion, but can have complex global behaviour. One might still hope that a significant portion of every such graph is well-organised, forming, say, a bipartite graph. We propose the following question: in a triangle-free graph of density d, what is the largest density in terms of d of a bipartite induced subgraph? We explore basic aspects of this new question, and show how it is connected to some central topics in probabilistic and extremal combinatorics.