DMS Combinatorics Seminar

Speaker: Dr. Peter Johnson 

Title: Exact determination of minimum \((n,k,t)\) graphs among graphs with complete components

Abstract:  An \((n,k,t)\) graph is a simple graph on \(n\) vertices with the property that every induced subgraph on \(k\) vertices contains a complete subgraph on \(t\) vertices.  A minimum \((n,k,t)\) graph is an \((n,k,t)\) graph with a minimum number of edges.  The Strong \((n,k,t)\) Conjecture is that every such graph is a disjoint union (or “sum”) of complete graphs.  In previous work it has been shown that among such sums the graphs with the fewest edges are certain sums of isolated vertices with the complement of the Turan graph \(T(n – a,b)\), where \(a\) is the number of isolated vertices, \(a + b(t-1) = k – 1\), and \(b\) is in the set \(\{1,…,B\}\) in which \(B = B(n,k,t)\) is explicitly given in terms of \(n\), \(k\), and \(t\).   The defect in this result is that it gives no clue as to where in that set b might be found. Last summer a group of 5 REUers determined exactly where in that set of consecutive integers the optimal value(s) of \(b\) is(are) to be found.  This is their story.