Talks & Seminars
Extremal Graph Theory
Prof. Ajit Diwan, IITB
Date & Time: October 17, 2007 10:45
Venue: F. C. Kohli Auditorium, KR building
The basic question in extremal graph theory is: What is the maximum number of edges in a simple graph with n vertices that does not contain a specified graph H as a subgraph? This number is denoted ex(n,H).

Extremal graph theory originated in 1906 when Mantel showed that ex(n,K_3) = n^2/4 for even n and (n^2-1)/4 for odd n. (K_3 is the complete graph with 3 vertices, also called a triangle.) Turan (1941) generalized this and showed that ex(n,K_t) <= \frac{(t-2)}{2(t-1)}n^2 with equality when n is a multiple of (t-1). Turan's theorem is considered important mainly due to the variety of ways in which it can be proved using different techniques. These techniques have been useful for many other problems.

The main part of the talk will be on a generalization of Turan's theorem that we have been working on. Suppose there are two types of edges, red and blue. A pair of vertices may be joined by a red edge, a blue edge, both a red and blue edge, or no edge at all. Now the basic question is: What is the largest number m such that there is a graph with n vertices, m red edges and m blue edges, that does not contain a specified red-blue edge-coloured graph H as a subgraph? We denote this number m by ex(n,H,2).

Our main conjecture is that, barring some exceptional cases, ex(n,K_t,2) <= \frac{(t-2)}{2(t-1)}n^2, where K_t denotes an arbitrarily red-blue edge-coloured complete graph with t vertices. The exceptional cases occur for t = 4, 6 and 8. We have proved this conjecture for t = 3,4,5 and for edge-colourings of K_t that contain a monochromatic K_{t-1}, for all t.

This is joint work with Dhruv Mubayi (Univ. Illinois at Chicago).
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback