## Organizer(s) | Jeffry Kahn, Jacob D Baron, Patrick Devlin | ## Archive |

## Upcoming Talks

## Monday, November 30th |

## Boris Bukh, |

## "Ranks of matrices with few distinct entries" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: Many applications of linear algebra method to combinatorics rely on the bounds on ranks of matrices with few distinct entries and constant diagonal. In this talk, I will explain some of these application. I will also present a classification of sets L for which no low-rank matrix with entries in L exists. |

## Past Talks

## Monday, November 23rd |

## Ameera Chowdhury, |

## "Inclusion Matrices and the MDS Conjecture" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: Let F_q be a finite field of order q with characteristic p. An arc is an ordered family of vectors in (F_q)^k in which every subfamily of size k is a basis of (F_q)^k. The MDS conjecture, which was posed by Segre in 1955, states that if k <= q, then an arc in (F_q)^k has size at most q+1, unless q is even and k=3 or k=q-1, in which case it has size at most q+2.
We propose a conjecture which would imply that the MDS conjecture is true for almost all values of k when q is odd. We prove our conjecture in two cases and thus give simpler proofs of the MDS conjecture when k <= p, and if q is not prime, for k <= 2p-2. To accomplish this, given an arc G of (F_q)^k and a nonnegative integer n, we construct a matrix M_G^{uparrow n}, which is related to an inclusion matrix, a well-studied object in combinatorics. Our main results relate algebraic properties of the matrix M_G^{uparrow n} to properties of the arc G and may provide new tools in the computational classification of large arcs. |

## Monday, November 16th |

## Jed Yang, |

## "Tiling with triangles is hard" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: Knutson, Tao, and Woodward introduced puzzle pieces consisting of two triangles and a rhombus (with edge labels). They proved that tilings by these puzzle pieces (allowing rotations) of triangular regions (with edge labels) are counted by Littlewood-Richardson coefficients, which are numbers that appear naturally in many contexts.
Together with the saturation conjecture, proved by Knutson and Tao, this means, in particular, that tileability of triangular regions by puzzle pieces can be decided in polynomial time. In this talk, we will discuss the problem of tiling arbitrary regions with these puzzle pieces. Regardless of whether reflections are allowed when tiling, the problem is NP-complete. Joint work with Igor Pak. |

## Monday, November 9th |

## Huseyin Acan, |

## "Indecomposability threshold for random permutations" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: A permutation of n is indecomposable if no proper initial segment is a permutation of an integer less than n. Consider a permutation a(n,m) chosen uniformly at random from the set of permutations of n with exactly m inversions. This permutation is decomposable for small m and indecomposable for large m (with probability approaching 1 as n tends to infinity). I will talk about a threshold m(n) around which the transition from 'being decomposable' to 'being indecomposable' occurs and also the number of indecomposable components a(n,m) when m is slightly below the threshold.
Joint work with Boris Pittel. |

## Monday, November 2nd |

## Jan Vondrak, |

## "Algorithmic proof of the Lovasz Local Lemma via resampling oracles" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: For a collection of events on a probability space with specified dependencies, the Lovasz Local Lemma ("LLL") gives a sufficient condition for the existence of a point avoiding all the events. Following Moser's discovery of an efficient algorithm for many applications of the Lovasz Local Lemma, there has been extensive research on various extensions of this result. We present a unifying algorithmic proof of the Lovasz Local Lemma (and its stronger variants such as Shearer's Lemma), independent of the underlying probability space, using what we call "resampling oracles". As a consequence, we obtain efficient algorithms for the known settings where the LLL applies (independent random variables, random permutations, perfect matchings, spanning trees). We present some new applications, in particular a new result on packings of rainbow spanning trees.
(joint work with Nick Harvey) |

## Monday, October 26th |

## Noga Alon, |

## "Coloring and Girth" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: The study of graphs with high girth and high chromatic number had a profound influence on the history of Combinatrics and Graph Theory, and led to the development of sophisticated methods involving tools from topology, number theory, algebra and combinatorics.
I will discuss the topic focusing on a recent new explicit construction of graphs (and hypergraphs) of high girth and high chromatic number, in joint work with Kostochka, Reiniger, West and Zhu.TBA |

## Monday, October 19th |

## Maria Chudnovsky, |

## "Induced cycles and coloring" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: The Strong Perfect Graph Theorem states that graphs with no induced odd cycle of length at least five, and no complements of one behave very well with respect to coloring. But what happens if only some induced cycles (and no complements) are excluded? Gyarfas made a number of conjectures on this topic, asserting that in many cases the chromatic number is bounded by a function of the clique number. In this talk we discuss recent progress on some of these conjectures.
This is joint work with Alex Scott and Paul Seymour. |

## Monday, October 12th |

## John Kim, |

## "A Cauchy-Davenport theorem for linear maps" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: We prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets A and B of the finite field F_p, the classical Cauchy-Davenport theorem gives a lower bound for the size of the sumset A+B in terms of the sizes of the sets A and B. Our theorem considers a general linear map L:F_p^n -> F_p^m and subsets A_1, ..., A_n of F_p, and gives a lower bound on the size of L(A_1 x A_2 x ... x A_n) in terms of the sizes of A_1, ..., A_n. Our proof uses Alon's Combinatorial Nullstellensatz and a variation of the polynomial method.
Joint work with Simao Herdade and Swastik Kopparty |

## Monday, October 5th |

## Krzysztof Choromanski, |

## "The Erdos-Hajnal Conjecture, structured non-linear graph-based hashing and b-matching anonymization via perfect matchings counting" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: The goal of this talk is to show three new combinatorial techniques that led to some recent advances in discrete mathematics and computer science in general.
The first one regards the celebrated open conjecture of Erdos and Hajnal from 1989 stating that families of graphs not having some given graph H as an induced subgraph contain polynomial-size cliques/stable sets (in the undirected setting) or transitive subsets (in the directed setting). Recent techniques that I will be talking about in this part of the talk provided the proof of the conjecture for new infinite classes of graphs. Furthermore, they gave tight asymptotics for the Erdos-Hajnal coefficients for many classes of prime tournaments as well as the proof of the weaker version of the conjecture for trees on at most six vertices and all but one tournament on at most six vertices. Structured non-linear graph-based hashing is motivated by applications in neural networks, where matrices of linear projections are constrained to have a specific structured form. This drastically reduces the size of the model and speeds up computations. I will show how the properties of the underlying graph encoding correlations between entries of these matrices (such as its chromatic number) imply the quality of the entire non-linear hashing mechanism. Furthermore, I will explain how general structured matrices that very recently attracted researchers attention naturally lead to the underlying graph theory description. The last topic covers combinatorial results regarding the number of perfect matchings containing some fixed partial matching in the bipartite graph. Those results provide theoretical guarantees regarding privacy level achieved by several new graph-based anonymization algorithms such as b-matching. |

## Monday, September 28th |

## Elchanan Mossel, |

## "Strong contraction and influences in tail spaces" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: Various motivations recently led Mendel and Naor, Hatami and Kalai to study functions in tail spaces - i.e. function all of whose low level Fourier coefficients vanish. I will discuss the questions and conjectures that they posed and our recent work which resolves some of these questions and conjectures. Based on a joint work with Steven Heilman and Krzysztof Oleszkiewicz. |

## Monday, September 21st |

## Toby Johnson, |

## "The second eigenvalue of dense random regular graphs" |

Time: 2:00 PM |

Location: Hill 425 |

Abstract: Consider a random d-regular graph on n vertices. Its second eigenvalue is closely related to its expansion properties, and bounding it has been a major topic of research over the last thirty years. It's conjectured by Van Vu that as n and optionally d tend to infinity, the second eigenvalue is bounded by C*sqrt(d) with probability tending to 1, so long as d remains between 3 and n-3. This is currently known to hold only if d = o(n^(1/2)). We show that it holds so long as d remains smaller than n^(2/3). We use the Kahn-Szemeredi approach, which is based on showing concentration for Rayleigh quotients of the graph's adjacency matrix. We develop new techniques based on Stein's method for proving these concentration results. Our machinery gives proofs vastly simpler than previous ones based on martingales. This is joint work with Nicholas Cook and Larry Goldstein. |