Omschrijving |
**Title: **
A new basic question about triangle-free graphs
**Abstract: **
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), Blanches 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.
Joint work with Louis Esperet and Stéphan Thomassé. |