Mathematics Department - Discrete Math - Fall 2016

# Discrete Math - Fall 2016

### Organizer(s)

Jeffry Kahn, Jacob D Baron, Patrick Devlin

## Monday, October 24th

### "Long range order in random three-colorings of Z^d"

Time: 2:00 PM
Location: Hill 705
Abstract: Consider a random coloring of a bounded domain in the bipartite graph Z^d with the probability of each color configuration proportional to exp(-beta*N(F)), where beta>0, and N(F) is the number of nearest neighboring pairs colored by the same color. This model of random colorings biased towards being proper, is the antiferromagnetic 3-state Potts model from statistical physics, used to describe magnetic interactions in a spin system. The Kotecky conjecture is that in such a model with d >= 3, Fixing the boundary of a large even domain to take the color 0 and high enough beta, a sampled coloring would typically exhibits long-range order. In particular a single color occupies most of either the even or odd vertices of the domain. This is in contrast with the situation for small beta, when each bipartition class is equally occupied by each of the three colors. We give the first rigorous proof of the conjecture for large d. Our result extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the beta=infinity case, where the coloring is chosen uniformly from all proper three-colorings. In the talk we shell give a glimpse into the combinatorial methods used to tackle the problem. These rely on structural properties of odd-boundary subsets of Z^d. No background in statistical physics will be assumed and all terms will be thoroughly explained. Joint work with Yinon Spinka.

## Monday, October 17th

### "Maximum number of edge-disjoint and almost-largest cliques in a random graph"

Time: 2:00 PM
Location: Hill 705
Abstract: Let omega be the clique number of the Erdos-Renyi graph G(n,1/2). It is known that omega is asymptotically 2log_2(n) and it is concentrated on two values (in most cases on just one value). For k=omega-4, Bollobas showed that, in G(n,1/2), the expected value of the size of a largest family of edge-disjoint k-cliques is at least (1+o(1))n^2/k^4. Later, Alon and Spencer conjectured that it is at least cn^2/k^2 for some constant c>0. We disprove the conjecture of Alon and Spencer by showing that this expectation is O(n^2/k^3). We also improve the lower bound to Omega(n^2log(k)/k^4). Joint with Jeff Kahn.

## Monday, October 10th

### "On a resilience version of the Littlewood-Offord problem"

Time: 2:00 PM
Location: Hill 705
Abstract: In this talk we consider a resilience version of the classical Littlewood-Offord problem. That is, consider the sum X=a_1x_1+...a_nx_n, where the a_i-s are non-zero reals and x_i-s are i.i.d. random variables with P(x_1=1)=P(x_1=-1)=1/2. Motivated by some problems from random matrices, we consider the question: how many of the x_i-s can we typically allow an adversary to change without making X=0? We solve this problem up to a constant factor and present a few interesting open problems. Joint with: Afonso Bandeira (NYU) and Matthew Kwan (ETH, Zurich).

## Monday, September 26th

### "Capsets, sunflower-free sets in {0,1}^n, and the slice rank method"

Time: 2:00 PM
Location: Hill 705
Abstract: A collection of $k$ sets is said to form a $k$-sunflower, or $Delta$-system, if the intersection of any two sets from the collection is the same, and we call a family of sets $mathcal{F}$ sunflower-free if it contains no sunflowers. In this talk we will look at the recent breakthrough of Ellenberg and Gijswijt and Croot, Lev and Pach, which used polynomial method to obtain exponential upper bounds for the Capset problem, that is upper bounds for the size of the largest set in $mathbb{F}_3^n$ which contains no three term arithmetic progressions. In particular we will look at Tao's reformulation of this approach using the so called "Slice Rank Method," and apply it directly to the ErdH{o}s-Szemer'{e}di sunflower problem, proving an exponential upper bound for the size of any sunflower-free family of subsets of ${1,2,…,n}$.

## Monday, September 19th

### " The frog model on trees"

Time: 2:00 PM
Location: Hill 705
Abstract: Imagine that every vertex of a graph contains a sleeping frog. At time 0, the frog at one vertex wakes up and begins a simple random walk. When it moves to a new vertex, the sleeping frog there wakes up and begins its own simple random walk, which in turn wakes up any sleeping frogs it lands on, and so on. This process is called the frog model, and many basic questions about it remain open. I'll talk about the frog model on infinite trees, where the process exhibits some interesting phase transitions. In particular, I'll (mostly) answer a question posed by Serguei Popov in 2003 by showing that on a binary tree, all frogs wake up with probability one, while on a 5-ary or higher tree, some frogs remain asleep with probability one. This work is joint with Christopher Hoffman and Matthew Junge.

## Monday, September 12th

### "Induced subgraphs of graphs with large chromatic number"

Time: 2:00 PM
Location: Hill 705
Abstract: What can we say about the induced subgraphs of a graph G with very large chromatic number? If G has no large cliques, then what else can we guarantee? We will discuss recent work on this topic, and present some new results. (Joint work with Maria Chudnovsky and Paul Seymour.)

This page was last updated on February 09, 2016 at 10:04 am and is maintained by webmaster@math.rutgers.edu.