It is a well-known combinatorial exercise that among six people there are either three who mutually know each other or there are three who mutually don't know each other. In the language of graph theory one can formulate this fact by saying that for any two-coloring of the edges of the complete graph K6 there is a monochromatic triangle (a K3), we say that K6 is K3-Ramsey. On the other hand K6 is minimal with this property, i.e., there is a two-coloring of the edges of K6-e which does not contain a monochromatic triangle.
Nešetřil and Rödl, in a much more general theorem proved that not only we don't need a K6 in a K3-Ramsey graph, but we only need what we trivially need: triangles. More precisely, there is a graph H that is K3-Ramsey, and the clique number of H is 3. Ramsey's theorem ensures that for an arbitrary graph G there exists a large enough R(G), such that the clique KR(G) is G-Ramsey. Again, the theorem of Nešetřil and Rödl ensures the existence of G-Ramsey graphs whose clique number is equal to the clique number of G.
Goal: The goal of the project is to further study various properties of H-Ramsey graphs, in particular minimal H-Ramsey graphs for different "small" H, for example K3 and C4. A possible starting point could be the following extremal question: Determine/bound the smallest number of vertices ni on which there exists a K3-Ramsey graph whose clique number is i (i=3,4,5). It is known that n6=6.
Prerequisites: Acquaintance with graph theory and combinatorics. Should exhaustive search problems arise, some programming skill would come in handy.
Contact Persons:
Tibor Szabó,
szabo@inf.ethz.ch, CAB G 31.2,
Tel: (044) 632-0858.
Philipp Zumstein,
zuphilip@inf.ethz.ch,
CAB G 17, Tel: (044) 632-7318.