離散幾何構造セミナー: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.

(世話人:吉永)

関連項目
,

研究集会・セミナー・集中講義の一覧へ