## Seminars and Colloquia by Series

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.
Tuesday, February 10, 2015 - 12: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.
Tuesday, February 3, 2015 - 12: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.
Tuesday, January 27, 2015 - 12:05 , Location: Skiles 005 , Megan Bernstein , Stanford University , , Organizer: Prasad Tetali
When studying the mixing of random walks on groups, information about the relative likelihoods of the elements under the walk can serve to help understand the mixing and reveal some internal structure. Starting with some elementary arguments of Diaconis and Isaacs and moving into arguments using representation theory of the symmetric group, I'll demonstrate some total and partial orders on finite groups that describe the relative likeliness under random walks. No prior knowledge is assumed.
Thursday, January 22, 2015 - 12:05 , Location: Skiles 005 , Peter Csikvari , MIT , , Organizer: Prasad Tetali
In this talk we will survey some recent development on statistical properties of matchings of very large and infinite graphs. The main goal of the talk is to describe a few applications of a new concept called matching measure. These applications include new results on the number of (perfect) matchings in large girth graphs as well as simple new proofs of certain statistical physical theorems. In particular, we will sketch the proof of Friedland's Lower Matching Conjecture, and a new proof of Schrijver's and Gurvits's theorems. This talk is based on joint papers with various subsets of Miklos Abert, Peter E. Frenkel, Tamas Hubai and Gabor Kun.
Tuesday, January 13, 2015 - 12:05 , Location: Skiles 005 , Emma Cohen , Georgia Tech , Organizer: Prasad Tetali
Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. We consider natural local moves on some realizations of the Catalan sequence and derive estimates of the mixing time of the corresponding Markov chains. We present a new O(n^2 log n) bound on the mixing time for the random transposition chain on Dyck paths, and raise several open problems, including the optimality of the above bound.  (Joint work with Prasad Tetali and Damir Yelliusizov.)
Tuesday, January 6, 2015 - 12:05 , Location: Skiles 005 , Hiep Han , Emory University and University of Sao Paulo, Brazil , , Organizer: Prasad Tetali
Let B(d,n) denote the d-regular graph on n vertices which consists of the disjoint union of complete bipartite graphs. It follows from the results of Kahn and of Zhao that among all d-regular graphs on n vertices B(d,n) maximizes the number of independent sets. In this talk, we show a spectral stability phenomenon of this result in the following sense. The eigenvalues of (the adjacency matrix) of B(d,n) are known to be d, -d and zeroes and  we show that, if the smallest eigenvalue of G is bounded away from -d, then the number of independent sets in G is exponentially smaller than that of B(d,n). Furthermore, we extend this method to study the well-known hard-core model from statistical physics. Given a d-regular bipartite graph G whose second smallest eigenvalue is bounded away from -d. Let Ind(G) denote the set of all independent sets of G. Among others, we show that in this case the random independent set I\in Ind(G), drawn from the hard-core distribution with activation parameter lambda>> (log d)/d, is essentially completely (up to o(|I|) vertices) contained in one of the partition classes of G. (This is joint work with Prasad Tetali.)
Tuesday, December 9, 2014 - 13:35 , Location: Skiles 005 , Maksim Zhukovskii , MIPT, Moscow, Russia , Organizer: Prasad Tetali
In the talk, an asymptotic behaviour of first order properties of the Erdos-Renyi random graph G(n,p) will be considered. The random graph obeys the zero-one law if for each first-order property L either its probability tends to 0 or tends to 1. The random graph obeys the zero-one k-law if for each property L which can be expressed by first-order formula with quantifier depth at most k either its probability tends to 0 or tends to 1. Zero-one laws were proved for different classes of functions p=p(n). The class n^{-a} is at the top of interest. In 1988 S. Shelah and J.H. Spencer proved that the random graph G(n,n^{-a}) obeys zero-one law if a is positive and irrational. If a is rational from the interval (0,1], then G(n,n^{-a}) does not obey the zero-one law. I obtain zero-one k-laws for some rational a from (0,1]. For any first-order property L let us consider the set S(L) of a from (0,1) such that a probability of G(n,n^{-a}) to satisfy L does not converges or its limit is not zero or one. Spencer proved that there exists L such that S(L) is infinite. Recently in the joint work with Spencer we obtain new results on a distribution of elements of S(L) and its limit points.
Tuesday, December 2, 2014 - 13:30 , Location: Skiles 005 , Laura Florescu , Courant Institute, NYU , Organizer: Prasad Tetali
In a "rotor walk" the exits from each vertex follow a prescribed periodic sequence. On an infinite Eulerian graph embedded periodically in $\R^d$, we show that any simple rotor walk, regardless of rotor mechanism or initial rotor configuration, visits at least on the order of t^{d/(d+1)} distinct sites in t steps. We prove a shape theorem for the rotor walk on the comb graph with i.i.d.\ uniform initial rotors, showing that the range is of order t^{2/3} and the asymptotic shape of the range is a diamond. Using a connection to the mirror model and critical percolation, we show that rotor walk with i.i.d. uniform initial rotors is recurrent on two different directed graphs obtained by orienting the edges of the square grid, the Manhattan lattice and the F-lattice. Joint work with Lionel Levine and Yuval Peres.