Our main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently. Joint work with Jeff Kahn.
Joint work with Pascal Maillard.
Includes joint work with Nayantara Bhatnagar, Evita Nestoridi, and Igor Pak.
Hiraguchi (1955) proved that any poset with n points has dimension at most n/2, which is sharp. We prove that the local dimension of a poset with n points is O(n/log n). To show that this bound is best possible, we use probabilistic methods to prove the following stronger result which extends a theorem of Chung, Erdős, and Spencer (1983): There is an n-vertex bipartite graph in which each difference graph cover of the edges will cover one of the vertices Θ(n/log n) times. (This is joint work with Jinha Kim, Ryan R. Martin, Tomáš Masařı́k, Warren Shull, Andrew Uzzell, and Zhiyu Wang)
(a) on Friday [September 29th, 1pm-2pm in Skiles 005] He Guo, will give an ACO Student Seminar on "Packing nearly optimal Ramsey R(3,t) Graphs"
(b) on Thursday [September 28th, 11am-12am in Skiles 006] Tom Bohman will give an ACO colloquim talk on "Randomized Controlled Trials for Combinatorial Construction"
(c) on Saturday and Sunday [September 30th and October 1st] Atlanta Lecture Series in Combinatorics and Graph Theory XX takes place at Georgia Tech, with featured speaker Paul Seymour