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.