110. Mathematical Colloquium

Uri Feige

Weizman Institute, Israel

ON RAMSEY MULTIPLICITIES AND HALF-RAMSEY GRAPHS

Wednesday December 5, 2018, 11:00
aula (refektar), 1st floor
MFF UK, Malostranské nám. 25, Praha 1

Abstract

Let c be largest such any graph on n vertices (for sufficiently large n) must contain a monochromatic subgraph (either a clique or an independent set) of size at least c log n (log in base 2). It is known that c is at least 1/2 [Erdös and Szekeres, 1935] and at most 2 [Erdös, 1947]. Narrowing the gap between these two bounds is a major open question in Ramsey theory.

Let d be largest such that any graph on n vertices must contain at least n^{d log n} monochromatic subgraphs. Erdös [1962] showed that d is at least c/4 and at most 1/2. Szekely [1984] showed that d > 0.157, which is strictly larger than c/4 if c = 1/2. Furthermore, he showed that if Half-Ramsey graphs exist (graphs for which c = 1/2) then in these graphs, for every constant c', the number of monochromatic subgraphs of size c' log n is at most n^{g(c) log n} (up to low order terms). Here g is a function that is monotonically increasing from 0 to roughly 0.32 in the domain [0, 1/2].

We will present a relatively simple proof showing that d is at least 1/4. Moreover, we show that if Half-Ramsey graphs exist, then in such graphs the function g introduced by Szekeley is not only an upper bound on the number of monochromatic subgraphs of any given size, but also a lower bound. Hence in Half-Ramsey graphs, if they exist, the number of monochromatic subgraphs of size (log n)/2 is roughly n^{0.32 log n}, but there are no monochromatic subgraphs of slightly larger size.

About the speaker

Uriel (Uri) Feige studoval na Technionu a na Weizmanově institutu, kde získal v roce 1992 doktorát. Poté byl postdokem na předních institucích (IBM Yorktown Heights, Princeton University) a posléze byl zaměstnán na Weizmanově institutu, od roku 2003 jako řádný profesor. Delší dobu působil v prestižní Theory Group, Microsoft Research.

Aktivita prof. Feigeho je rozsáhlá a pokrývá v podstatě celou teoretickou infor matiku a příbuzné oblasti kombinatoriky, náhodných struktur a diskrétní geometrie. Vysoká úroveň jeho činnosti byla oceněna opakovaně na mezinárodní úrovni, zmiňme zde pouze Gödelovu cenu (2001) a zvanou přednášku na Mezinárodním kongresu matematiků (2002). Uri Feige je však velmi aktivní v mezinárodním kontextu, což dokládá skutečnost, že byl v programovúch výborech vpodstatě všech významných mezinárodních konferencí v oblasti teoretické informatiky.