Combinatorics Seminar

Speaker: Pete Johnson

Title: Minimum (n,k,t) graphs

Abstract: Suppose that n, k, and t are positive integers, in non-increasing order. An (n,k,t) graph is a simple graph on n vertices such that every induced subgraph on k vertices has a complete subgraph on t vertices. A minimum (n,t,k)graph is an (n,k,t)graph with the minimum number of edges possible for such a graph. The case t = 2 is intriguing because the unique minimum (n,k,2) graph is the complement of the Turan graph on n vertices with k - 1 parts, by Turan's theorem.

Our (Dean Hoffman's, Jessica McDonald's, and my) conjecture is that for every n, k,and t, there is a minimum (n,k,t) graph whose every component is a clique--call it a cligue graph, for short. This talk will show how to obtain, for each n, k, and t,  all graphs with the minimum number of edges among (n,k,t) graphs which are clique graphs.