Seminars and Colloquia by Series

Friday, September 18, 2015 - 15:00 , Location: Skiles 005 , Tom Hayes , The University of New Mexico , , Organizer: Esther Ezra
In the Rendezvous problem on the complete graph, two parties are trying to meet at some vertex at the same time, despite starting out with independent random labelings of the vertices. It is well known that the optimal strategy is for one player to wait at any vertex, while the other visits all n vertices in consecutive steps, which guarantees a rendezvous within n steps and takes (n + 1)/2 steps on average. This strategy is very far from being symmetric, however. E. Anderson and R. Weber presented a symmetric algorithm that achieves an expected meeting time of 0.829n, which has been conjectured to be optimal in the symmetric setting. We change perspective slightly: instead of trying to minimize the expected meeting time, we try to maximize the probability of successfully meeting within a specified number of timesteps. In this setting, for all time horizons that are linear in n, the Anderson-Weber strategy has a constant probability of failure. Surprisingly, we show that this is not optimal: there exists a different symmetric strategy that almost surely guarantees meeting within 4n timesteps. This bound is tight, in that the factor 4 cannot be replaced by any smaller constant. Our strategy depends on the construction of a new kind of combinatorial object that we dub”rendezvous code.”On the positive side, for T < n, we show that the probability of meeting within T steps is indeed (approximately) maximized by the Anderson-Weber strategy. Our results imply new lower bounds on the expected meeting time for any symmetric strategy, which establishes an asymptotic difference between the best symmetric and asymmetric strategies. Finally, we examine the symmetric rendezvous problem on other vertex-transitive graphs.
Wednesday, September 16, 2015 - 16:00 , Location: Skiles 006 , Imre Leader , University of Cambridge , , Organizer: Esther Ezra
Let $T$ be a finite subset of  ${\Bbb Z}^n$. It may or may not tile  ${\Bbb Z}^n$, in the sense of  ${\Bbb Z}^n$ having a partition into copies of $T$. But is there a dimension $d$ such that $T$ does tile  ${\Bbb Z}^d$ ? Our talk will focus on this question.
Friday, September 11, 2015 - 15:00 , Location: Skiles 005 , Megan Bernstein , Georgia Tech , Organizer: Esther Ezra
I will find upper and lower bounds for the mixing time as well as the likelihood order after sufficient time of the following involution walk on the symmetric group. Consider 2n cards on a table. Pair up all the cards. Ignore each pairing with probability $p \geq 1/2$. For any pair not being ignored, pick up the two cards and switch their spots. This walk is generated by involutions with binomially distributed two cycles. The upper bound of $\log_{2/(1+p)}(n)$ will result from spectral analysis using a combination of a series of monotonicity relations on the eigenvalues of the walk and the character polynomial for the representations of the symmetric group. A lower bound of $\log_{1/p}$ differs by a constant factor from the upper bound. This walk was introduced to study a conjecture about a random walk on the unitary group from the information theory of black holes.
Tuesday, May 19, 2015 - 13:30 , Location: Skiles 005 , Annachiara Korchmaros , University of Basilicata , Organizer: Christine Heitsch
In the study of combinatorial aspects of symmetric groups, a major problem arising from applications to Genetics consists in finding a minimum factorization of any permutation with factors from a given generating set. The difficulty in developing an adequate theory as well as the hardness of the computational complexity may heavily vary depending on the generator set. In this talk, the generating set consists of all block transpositions introduced by Bafna and Pevzner in 1998 for the study of a particular ''genome rearrangement problem''. Results, open problems, and generalizations are discussed in terms of Cayley graphs and their automorphism groups.
Tuesday, April 21, 2015 - 12:00 , Location: Skiles 005 , Brandon Hanson , University of Toronto , Organizer: Ernie Croot
Characters are a central tool for understanding arithmetic. For example, the most familiar character is the Legendre symbol, which detects the quadratic residues. In this talk I will present a few ideas as to how character sums may be useful in arithmetic combinatorics and vice versa.  Traditionally, estimates for character sums have been used to count arithmetic configurations of interest to the combinatorialist. More recently, arithmetic combinatorics has proved useful in the estimation of certain character sums. Many character sums are easy to estimate provided they have enough summands - this is sometimes called the square-root barrier and is a natural obstruction. I will show how the sum-product phenomenon can be leveraged to push past this barrier.
Tuesday, April 7, 2015 - 12:05 , Location: Skiles 005 , Chi Ho Yuen , Georgia Tech , , Organizer: Prasad Tetali
The Jacobian group Jac(G) of a finite graph G is a group whose cardinality is the number of spanning trees of G. G also has a tropical Jacobian which has the structure of a real torus; using the notion of break divisors, one can obtain a polyhedral decomposition of the tropical Jacobian where vertices and cells correspond to the elements of Jac(G) and the spanning trees of G respectively. In this talk I will give a combinatorial description to bijections coming from this geometric setting, I will also show some previously known bijections can be related to these geometric bijections. This is joint work with Matthew Baker.
Tuesday, March 31, 2015 - 12:05 , Location: Skiles 005 , Torsten Muetze , ETH (Zurich) and Georgia Tech , , Organizer: Prasad Tetali
Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length 2n+1 that have exactly n or n+1 entries equal to 1, with an edge between any two vertices for which the corresponding bitstrings differ in exactly one bit. The middle levels conjecture asserts that this graph has a Hamilton cycle for every n>=1. This conjecture originated probably with Havel, Buck and Wiedemann, but has also been (mis)attributed to Dejter, Erdos, Trotter and various others, and despite considerable efforts it remained open during the last 30 years. In this talk I present a proof of the middle levels conjecture. In fact, I show that the middle layer graph has 2^{2^{\Omega(n)}} different Hamilton cycles, which is best possible. and
Tuesday, March 10, 2015 - 12:05 , Location: Skiles 005 , Joshua Zahl , MIT , , Organizer: Prasad Tetali
In 2010, Guth and Katz proved that if a collection of N lines in R^3 contained more than N^{3/2} 2-rich points, then many of these lines must lie on planes or reguli. I will discuss some generalizations of this result to space curves in three dimensional vector spaces. This is joint work with Larry Guth.
Wednesday, February 18, 2015 - 16:00 , Location: Skiles 005 , Nathan McNew , Dartmouth College , Organizer: Ernie Croot
We look at two combinatorial problems which can be solvedusing careful estimates for the distribution of smooth numbers.  Thefirst is the Ramsey-theoretic problem to determine the maximal size ofa subset of of integers containing no 3-term geometric progressions.This problem was first considered by Rankin, who constructed such asubset with density about 0.719. By considering progressions among thesmooth numbers, we demonstrate a method to effectively compute thegreatest possible upper density of a geometric-progression-free set.Second, we consider the problem of determining which prime numberoccurs most frequently as the largest prime divisor on the interval[2,x], as well as the set prime numbers which ever have this propertyfor some value of x, a problem closely related to the analysis offactoring algorithms.
Monday, February 16, 2015 - 15:05 , Location: Skiles 005 , Spencer Backman , University of Rome , Organizer: Matt Baker
A fourientation of a graph is a choice for each edge of whether to orient it in either direction, bidirect it, or leave it unoriented. I will present joint work with Sam Hopkins where we describe classes of fourientations defined by properties of cuts and cycles whose cardinalities are given by generalized Tutte polynomial evaluations of the form: (k+l)^{n-1}(k+m)^g T (\frac{\alpha k + \beta l +m}{k+l}, \frac{\gamma k +l + \delta m}{k+m}) for \alpha,\gamma \in {0,1,2} and \beta, \delta \in {0,1}. We also investigate classes of 4-edge colorings defined via generalized notions of internal and external activity, and we show that their enumerations agree with those of the fourientation classes. We put forth the problem of finding a bijection between fourientations and 4-edge-colorings which respects all of the given classes. Our work unifies and extends earlier results for fourientations due to myself, Gessel and Sagan, and Hopkins and Perkinson, as well as classical results for full orientations due to Stanley, Las Vergnas, Greene and Zaslavsky, Gioan, Bernardi and others.