離散幾何構造セミナー：A new basic question about triangle-free graphs, Ross Kang (RU Nijmegen)

開催日時

2018年10月25日 10時30分 ～ 2018年10月25日 12時00分

場所

3-413

講演者

Ross Kang

離散幾何構造セミナー

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.

世話人：吉永