Dense triangle-free digraphs

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=aLi5KftzVjk


Duration: 36:17
333 views
4

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.



Other Videos By Microsoft Research


2016-09-06Linked Decompositions of Networks and Polya Urns with Choice
2016-09-06The Light Portal: 3D Reconstruction and Visualization over Space and Time
2016-09-06Distributed Speculative Execution: A Programming Model for Reliability and Increased Performance
2016-09-06Director of MITΓÇÖs Auto-ID Laboratory and a professor of Information Engineering
2016-09-06Path invariants
2016-09-06Records, sums, cases, and exceptions: Row-polymorphism at work [1/9]
2016-09-06Internet 3.0: Ten Problems with Current Internet Architecture and Solutions for the Next Generation
2016-09-06The Bilateral Grid and a Topological Approach to Image Segmentation
2016-09-06Software Development Practices and Knowledge Sharing: A Comparison of XP & Waterfall Team Behaviors
2016-09-06How likely is BuffonΓÇÖs needle to meet a Cantor square?
2016-09-06Dense triangle-free digraphs
2016-09-06MOP: A Generic and Efficient Runtime Verification Framework
2016-09-06An Examination of User Behaviour during Web Information Tasks
2016-09-06Modeling Science: Topic models of Scientific Journals and Other Large Document Collections
2016-09-06Exhaustive Phase Order Search Space Exploration and Evaluation
2016-09-06Supervised Dimensionality Reduction with Principal Component Analysis
2016-09-06Network Market Design for Efficient Resource Allocation
2016-09-06Probabilistic Latent Variable Decompositions for Image and Audio Analysis
2016-09-06Improving Software Security with Precise Static and Runtime Analysis
2016-09-06What Analytical Performance Modeling Teaches Us About Computer Systems Design
2016-09-06A search engine for the real world, or, a top-down approach to vision


Tags:
microsoft research