Skip to ContentSkip to Navigation
Research Bernoulli Institute Calendar

Colloquium Mathematics, Dr. Ross Kang (RU Nijmegen) - A new basic question about triangle-free graphs

When:Tu 13-03-2018 16:00 - 17:00
Where:5161.0293 (Bernoulliborg)

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é.

Join us for tea/coffee at 15.30h!