The University of Michigan Combinatorics Seminar
Fall 2006
November 10, 4:10-5:00, 3866 East Hall

Cycles in dense digraphs

Maria Chudnovsky

Columbia University and Clay Institute


The Caccetta-Häggkvist conjecture is a problem in graph theory, quite simple to state, with connections in additive number theory and linear programming. It was proposed in 1978, and has remained open until now. The conjecture asserts the following. Let G be a directed graph with n vertices, and let t be an integer. Suppose that every vertex has at least n/t out-neighbors. Then the graph must have a directed cycle of length at most t. This has been settled when t is large, and the case t=3 seems the most important and challenging unsolved case.

It is easy to see that the Caccetta-Häggkvist conjecture holds for tournaments (these are directed graphs in which there is an edge between every two vertices), and, more generally, one might hope to take advantage of information about the density of the underlying graph. Thus, a related question is the following: given a directed graph D such that exactly k unordered pairs of vertices of D are non-adjacent in the underlying undirected graph, how many edges does one need to delete in order to make the directed graph acyclic? We conjecture that the right answer is k/2. We prove this in some special cases, and show an infinite family of examples where this is tight. We also prove a weaker version of the conjecture, with k/2 replaced by k.

This is joint work with Paul Seymour and Blair Sullivan.