Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Carnegie Mellon University Title: The diamond-free process Abstract: For a fixed graph H, the H-free process is the following random graph process. Starting with n isolated vertices, at each step add a new edge chosen uniformly at random from the non-edges whose addition does not create a (not necessarily induced) copy of H. This process terminates with a maximal H-free graph with a random number M(H) of edges.For most graphs H containing a cycle, determining the likely asymptotic order of M(H) is an open problem. For H satisfying a particular density condition (strict 2-balancedness), likely lower bounds are known which are conjectured to be optimal, and which have been shown to be for only a few special cases: K3, K4, and cycles of any fixed length. But far less is known for graphs H not satisfying that density condition, with the smallest nontrivial example being the diamond graph, formed by removing an edge from K4. This talk will focus on the diamond-free process (for which we now know the right order of M(H)) and some of the interesting and unexpected complications that arise in its analysis. Date: Thursday, March 27, 2014 Time: 3:30 pm Location: Wean Hall 8220 Submitted by: Boris Bukh |