Microsoft Research Audio 103993: 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.

©2007 Microsoft Corporation. All rights reserved.