Forbidden and Colored Subgraphs

Emory University, Atlanta GA

Investigators

Abstract

An n by n Latin square is an n by n square filled with n different symbols, each of which occurs exactly once in each row and column. This definition might remind the reader of a commonly known puzzle called ‘sudoku’ which is a 9 by 9 Latin square with some additional constraints. The study of Latin squares dates back to the 1700s to the work of Euler. Latin squares have connections to various subfields in mathematics. For example, they are multiplication tables of quasigroups from algebra, they are used as error-correcting codes when one wishes to transmit data via a noisy channel such as power lines, etc. No matter how one fills a 3 by 3 Latin square, it is always possible to pick three cells, no two of which share a row, a column or a symbol. Such a collection of cells is called a transversal. In contrast, it is not possible to find a transversal in a two by two Latin square. A famous conjecture from the 1960s due to Ryser asserts that for odd n, it is always possible to find a transversal in an n by n Latin square. In the graph theoretic language, this is equivalent to the problem of finding a so-called rainbow matching in a properly edge-colored complete bipartite graph with partition sizes equal to n. This project aims to explore various problems which are related to finding certain rainbow structures in colored graphs. The current project, while combinatorially stated, has connections to other fields of mathematics, such as discrete geometry and algebra, and solutions will likely involve some use of algebraic and probabilistic methods thus creating further connections between combinatorics and other fields of mathematics. Graduate students will be trained as part of this project. In this project we will explore questions related to the existence of various spanning and non-spanning colored structures in colored graphs. A rainbow subgraph of a colored graph is a subgraph in which each edge has a distinct color. We plan to work on questions that have two common themes at heart. The first one is understanding the structure and properties of an object, for example, a graph, given it does not contain some forbidden sub-object, for example, a rainbow subgraph. These can be viewed as Turan-type problems adapted to the colored setting, where one wants to find, say the maximum number of edges in a properly edge-colored graph on a given number of vertices without containing a fixed rainbow subgraph. The second type of problems we will study is to find out under what restrictions a colored graph has certain spanning or almost-spanning rainbow subgraphs, such as long or Hamiltonian paths, spanning or almost spanning trees, a perfect or almost perfect matching. The problems to study include but are not limited to the existence of large rainbow matchings in graphs, existence of large matchings in hypergraphs, the existence of rainbow bases for vector spaces and matroids, Turan-type problems and their rainbow analogues such as the appearance of a rational number as a Turan exponent. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.