Erdos's Sunflower Lemma and Some Extremal Combinatorial Problems (February 2013)

Abstract

One of the open problems, due to Paul Erdos, concerns cardinality of a set system under constraints. Known as the Sunflower Lemma bound, this problem has remained open since 1960. We will begin with Sunflower Lemma and its connections to the problem of the talk. We will consider Sunflower Lemma's graph theoretic specialization and subsequent generalization to other extremal graph and hypergraph problems.

This talk will provide sharp bounds for the maximum number of edges possible in a simple graph with restricted values of two of the three parameters, namely, maximum matching size, independence number and maximum degree. We will also construct extremal graphs that achieve the edge bounds in all cases. We will further establish uniqueness of these extremal graphs whenever they are unique. We will also provide some other results on cardinality of the edge set of a graph that generalize a previously known result due to Erdos and Gallai.

Finally, we will discuss similar results on cardinality of hypergraphs under constraints.

The work is inspired by previous work on extremal graphs and set systems by  H.L. Abbott; V. Chvatal and D. Hanson;  Balachandran and Khare, D. Hanson and N. Sauer; Erdos and Gallai; Erdos and Rado; and P. Frakel.

This seminar is organized by the Department of Mathematics and Statistics, AUS College of Arts and Sciences.

For further details, kindly contact [email protected].