IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Applications of Linear Algebra to Forbidden Configurations

  • March 28, 2013
  • 2 p.m.
  • LeConte 312

Abstract

Linear algebra is occasionally useful in proving combinatorial bounds. Fisher's inequality for block designs is proven this way. We give some proofs of important bounds for Forbidden Configurations using linear ' algebra. A typical idea is to associate with an $n\times 1$ $(0,1)$-column $(a _ 1,a _ 2,..,a _ n)^T$ with a multilinear polynomial in $n$ variables $x _ 1,x _ 2,..,x _ n$ so that the polynomial is nonzero for $(0,1)$ inputs if and only if $x _ 1=a _ 1, x _ 2=a _ 2$ etc. This idea has been applied to the basic Sauer Bound (Smolensky) and also in determining whether a $k$-rowed configuration $F$ has bound asymptotic to $m^k$ or $m^{k-1}$. The latter is joint work with Balin Fleming.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC