The Alon-Saks-Seymour and Rank-Coloring Conjectures
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
This thesis studies the Alon-Saks-Seymour Conjecture and the Rank-Coloring Conjecture and their relationships to computer science. For a graph G, the chromatic number, x(G), is the minimum number of colors needed to properly color the vertices of G. If A(G) is the adjacency matrix of G, then rank(A(G)) denotes its rank. The biclique partition number, bp(G), is the minimum number of complete bipartite subgraphs (bicliques) necessary to partition the edge set of G. The Rank-Coloring Conjecture states that for any graph G, x(G) <= rank(A(G)) and the Alon-Saks- Seymour Conjecture states that for any graph G, x(G) <= bp(G) + 1. Both of these conjectures have been previously disproven. In this thesis we construct an in nite family of graphs that are counterexamples to both conjectures. This construction generalizes previous work of Razborov and Huang and Sudakov. We discuss the relationship between these conjectures and questions in theoretical computer science relating to communication complexity, which is the amount of information that two parties need to exchange in order to compute some objective boolean function. We also discuss a generalization of biclique partitions to hypergraphs, where we consider the minimum number of complete r- partite r-uniform hypergraphs necessary to partition the edge set of the complete r-uniform hypergraph on n vertices.