EVENT DETAILS AND ABSTRACT

Title: Cycles in dense digraphs
Speaker: Professor Maria Chudnovsky
Speaker Info: Columbia University
Brief Description:
Special Note:
Abstract:

The Caccetta-Haggkvist 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-Haggkvist conjecture holds for tournaments (these are directed graph 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 with k non-adjacent pairs of vertices in the underlying undirected graph, and with no directed cycle of length at most three, 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 some natural 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.