Mathematics Department - Discrete Math - Fall 2016

Discrete Math - Fall 2016

Organizer(s)

Jeffry Kahn, Jacob D Baron, Patrick Devlin

Friday, December 9th

Special Discrete Math

"Latin squares and rainbow structures"

Time: 2:15 PM
Location: Hill 705
Abstract: This talk will be about transversals in Latin squares. A Latin square of order n is an n x n array filled with n symbols such that no symbol appears twice in the same row or column. Latin squares are classic objects introduced in the 18th century by Euler. Since then, they have found applications in group theory, coding theory, and the design of experiments.

A transversal in a Latin square is a set of entries no two of which share the same row, column, or symbol. In the 60s, conjectures arose about Latin squares having large transversals. Ryser conjectured that for odd n, every order n Latin square has a size n transversal. Brualdi and Stein conjectured that every Latin square has a size n - 1 transversal. This talk will focus on developing methods to approach the difficult Ryser-Brualdi-Stein Conjectures. In particular proofs will be discussed of approximate versions of two variants of the Ryser-Brualdi-Stein Conjectures - the Aharoni-Berger Conjecture and Andersen's Conjecture concerning rainbow structures in graphs.

Monday, December 12th

Special Discrete Math

"On the Erdos-Szekeres convex polygon problem"

Time: 2:00 PM
Location: Hill 705
Abstract: The classic 1935 paper of Erdos and Szekeres entitled "A combinatorial problem in geometry" was a starting point of a very rich discipline within combinatorics: Ramsey theory. In that paper, Erdos and Szekeres studied the following geometric problem. For every integer n geq 3, determine the smallest integer ES(n) such that any set of ES(n) points in the plane in general position contains n members in convex position, that is, n points that form the vertex set of a convex polygon. Their main result showed that ES(n) leq {2n - 4choose n-2} + 1 = 4^{n -o(n)}. In 1960, they showed that ES(n) geq 2^{n-2} + 1 and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has been made on the upper bound over the last 81 years. In this talk, we will sketch a proof showing that ES(n) =2^{n +o(n)}.

Monday, November 28th

"Permutation pattern densitites"

Time: 2:00 PM
Location: Hill 705
Abstract: The "pattern density" of a permutation pi in a permutation sigma is the fraction of subsequences of sigma (written in one-line form) that are ordered like pi. For example, the density of the pattern "12" in sigma is the number of pairs i < j with sigma(i) < sigma(j), divided by n choose 2. What does a typical permutation look like that has one or more pattern densities fixed? To help answer this we employ limit objects called "permutons," together with a variational principle that identifies the permuton that best represents a given class of permutations. Joint work with Rick Kenyon, Dan Kral' and Charles Radin.

Monday, November 21st

"Four conjectures in spectral extremal graph theory"

Time: 2:00 PM
Location: Hill 705
Abstract: We discuss how to prove four conjectures in extremal graph theory where the graph invariant being maximized is a function of the eigenvalues or eigenvectors of the adjacency matrix of the graph. Our most difficult result proves a conjecture of Boots and Royle from 1991: the planar graph of maximum spectral radius is the join of an edge and a path of length $n-2$. All of our proofs follow a similar template, and we will end the talk with several problems to which one might try to apply our method. This is joint work with Josh Tobin.

Monday, November 14th

"Configurations of lines in 3-space and rigidity of planar structures"

Time: 2:00 PM
Location: Hill 705
Abstract: Let $L=(ell_1,...,ell_n)$ be a sequence of $n$ lines in $R^3$. We define the {it intersection graph} $G_L = ([n], E)$ of $L$, where $[n] := {1,...,n}$, and with $(i,j)in E$ if and only if $i eq j$ and the corresponding lines $ell_i$ and $ell_j$ intersect, or are parallel (or coincide). For a graph $G = ([n], E)$, we say that a sequence $L$ realizes $G$ if $Gsubset G_L$. In the talk I will introduce a characterization of those graphs $G$, such that, every (generic) realization of $G$, consists of lines that are either all concurrent or all coplanar.

The result is inspired by connections we have found between configurations of lines in 3-space and the classical notion of graph rigidity of planar structures. The interaction goes in both directions: Properties established in the context of graph rigidity either can be interpreted directly as properties of line configurations in space, or lead the way to conjectures concerning the intersection patterns of lines in space. These general statements about lines in space, apart from their independent interest, can then be used back in the context of graph rigidity to get new information in this context. This will be illustrated in the talk.

Monday, November 7th

"Recent advances in explicit constructions of Ramsey graphs"

Time: 2:00 PM
Location: Hill 705
Abstract: In his 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of (2 log n)-Ramsey graphs on n vertices. Matching Erdős' result with a constructive proof is an intriguing problem in combinatorics that has gained significant attention in the literature. In this talk, we will present recent works towards this goal.

Monday, October 31st

"On the Sensitivity Conjecture"

Time: 2:00 PM
Location: Hill 705
Abstract: In this talk, we plan to discuss several recent results regarding the sensitivity conjecture. The sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely, the number of Hamming neighbors of x with different f-value). The well-known sensitivity conjecture of Nisan-Szegedy states that every sensitivity s Boolean function can be computed by a polynomial over the reals of degree poly(s). The conjecture is still wide open, as the best known upper bounds on degree are exponential rather than polynomial in s. 1. Based on joint work with Parikshit Gopalan, Rocco Servedio and Avi Wigderson, we prove an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L2) by a polynomial whose degree is O(s * log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Furthermore, we have examples demonstrating that our result is essentially tight. 2. Based on joint work with Shalev Ben-David and Pooya Hatami, we present new super-quadratic separations between the sensitivity and various decision tree complexities.

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.