Dense triangle-free digraphs

Given a directed tournament, the condition of being triangle-free (having no directed cycles of length at most three) forces the digraph to be acyclic. What can one say then about triangle-free digraphs which are almost tournaments (i.e. the number of non-edges is bounded)? In joint work with Maria Chudnovsky and Paul Seymour, we showed that all triangle-free digraphs with k non-edges can be made acyclic by deleting at most k edges. We conjecture that in fact, every such digraph can be made acyclic by deleting at most k/2 edges, and prove this stronger result for two classes of digraphs – circular interval digraphs, and those where the vertex set is the union of two cliques. In this talk, I will discuss these recent results and proof methods, as well as present several open problems relating to the conjecture. One of particular interest is a strengthening of the conjecture for some Cayley graphs, which can be reformulated in terms of a function on projective space.

Speaker Details

Blair D. Sullivan is currently a fourth year Ph.D. student in the Mathematics Department at Princeton University, working with Paul Seymour. She holds bachelors degrees in Applied Mathematics and Computer Science from Georgia Institute of Technology. Although her recent research has been concentrated on extremal problems in directed graph theory, she is interested in a variety of problems in combinatorics, especially those with connections to number theory.

Date:
Speakers:
Blair D. Sullivan
Affiliation:
Princeton University
    • Portrait of Jeff Running

      Jeff Running