## Seminars and Colloquia by Series

Friday, February 24, 2017 - 15:05 , Location: Skiles 005 , , Dartmouth College , , Organizer: Torin Greenwood
In enumerative combinatorics, it is quite common to have in hand a number of known initial terms of a combinatorial sequence whose behavior you'd like to study. In this talk we'll describe two techniques that can be used to shed some light on the nature of a sequence using only some known initial terms. While these methods are, on the face of it, experimental, they often lead to rigorous proofs. As we talk about these two techniques -- automated conjecturing of generating functions, and the method of differential approximation -- we'll exhibit their usefulness through a variety of combinatorial topics, including matchings, permutation classes, and inversion sequences.
Friday, February 17, 2017 - 15:05 , Location: Skiles 005 , , University of Louisville , Organizer: Fidel Barrera-Cruz
Many classical hard algorithmic problems on graphs, like coloring, clique number, or the Hamiltonian cycle problem can be sped up for planar graphs resulting in algorithms of time complexity $2^{O(\sqrt{n})}$. We study the coloring problem of unit disk intersection graphs, where the number of colors is part of the input. We conclude that, assuming the Exponential Time Hypothesis, no such speedup is possible. In fact we prove a series of lower bounds depending on further restrictions on the number of colors. Generalizations for other shapes and higher dimensions were also achieved. Joint work with E. Bonnet, D. Marx, T. Miltzow, and P Rzazewski.
Friday, February 10, 2017 - 15:05 , Location: Skiles 005 , Bartosz Walczak , Jagiellonian University in Kraków , , Organizer: Heather Smith
A class of graphs is *χ-bounded* if the chromatic number of all graphs in the class is bounded by some function of their clique number. *String graphs* are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are *χ*-bounded. In particular, it is known since 2012 that the class of all string graphs is not *χ*-bounded. We prove that for every integer *t*≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve *c* in at least one and at most *t* points is *χ*-bounded. This result is best possible in several aspects; for example, the upper bound *t* on the number of crossings of each curve with *c* cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called *k*-quasi-planar topological graphs. This is joint work with Alexandre Rok.
Friday, February 3, 2017 - 15:05 , Location: Skiles 005 , , Georgia Tech , , Organizer: Torin Greenwood
A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations are represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. There is an analogous polytope for conditional independence relations coming from any regular Gaussian model, and it can be defined using relative entropy.  For directed acyclic graphical models we give a construction of this polytope as a Minkowski sum of matroid polytopes.  The motivation came from the problem of learning Bayesian networks from observational data.  This is a joint work with Fatemeh Mohammadi, Caroline Uhler, and Charles Wang.
Friday, December 2, 2016 - 15:05 , Location: Skiles 005 , Ben Steinberg , CUNY , Organizer: Matt Baker
One can associate regular cell complexes to various objects from discrete and combinatorial geometry such as real and complex hyperplane arrangements, oriented matroids and CAT(0) cube complexes.  The faces of these cell complexes have a natural algebraic structure.  In a seminal paper from 1998, Bidigare, Hanlon and Rockmore exploited this algebraic structure to model a number of interesting Markov chains including the riffle shuffle and the top-to-random shuffle, as well as the Tsetlin library.  Using the representation theory of the associated algebras, they gave a complete description of the spectrum of the transition matrix of the Markov chain.  Diaconis and Brown proved further results on mixing times and diagonalizability for these Markov chains.  Bidigare also noticed in his thesis a natural connection between Solomon's descent algebra for a finite Coxeter group and the algebra associated to its Coxeter arrangement. Given, the nice interplay between the geometry, the combinatorics and the algebra that appeared in these two contexts, it is natural to study the representation theory of these algebras from the point of view of the representation theory of finite dimensional algebras.  Building on earlier work of Brown's student, Saliola, for the case of real central hyperplane arrangements, we provide a quiver presentation for the algebras associated to hyperplane arrangements, oriented matroids and CAT(0) cube complexes and prove that these algebras are Koszul duals of incidence algebras of associated posets.  Key to obtaining these results is a description of the minimal projective resolutions of the simple modules in terms of the cellular chain complexes of the corresponding cell complexes.This is joint work with Stuart Margolis (Bar-Ilan) and Franco Saliola (University of Quebec at Montreal)
Thursday, November 17, 2016 - 15:05 , Location: Skiles 269 , Andrew Suk , University of Illinois, Chicago , Organizer: Esther Ezra
Andew Suk will discuss some of the techincal details in his colloquium talk about the Erdos-Szekeres convex polygon problem. This is mainly an informal discussion.
Friday, November 11, 2016 - 15:00 , Location: Skiles 005 , Giorgis Petridis , University of Gerogia , Organizer: Ernie Croot
An expander polynomial in F_p, the finite field with p elements, is a polynomial f(x_1,...,x_n) such that there exists an absolute c>0 with the property that for every set A in F_p (of cardinality not particularly close to p) the cardinality of f(A,...,A) = {f(a_1,...,a_n) : a in A} is at least |A|^{1+c}. Given an expander polynomial, a very interesting question is to determine a threshold T so that |A|> T implies that |f(A,...,A)| contains, say, half the elements of F_p and so is about as large as it can be. For a large number of "natural appearing" expander polynomials like f(x,y,z) = xy+z and f(x,y,z) = x(y+z), the best known threshold is T= p^{2/3}. What is interesting is that there are several proofs of this threshold of very different “depth” and complexity. We will discuss why for the expander polynomial f(x,y,z,w) = (x-y)(z-w), where f(A,A,A,A) consists of the product of differences of elements of A, one may take T = p^{5/8}. We will also discuss the more complicated setting where A is a subset of a not necessarily prime order finite field.
Friday, November 4, 2016 - 15:05 , Location: Skiles 005 , , Kent State University , , Organizer: Galyna Livshyts
In this talk we will discuss an answer to a question of Alexander Koldobsky and present a discrete version of his slicing inequality.  We let $\# K$ be a number of integer lattice points contained in a set $K$. We show that for each $d\in \mathbb{N}$ there exists a constant $C(d)$ depending on $d$ only, such that for any origin-symmetric convex body $K \subset \mathbb{R}^d$ containing $d$ linearly independent lattice points  $$\# K \leq C(d)\text{max}_{\xi \in S^{d-1}}(\# (K\cap \xi^\perp))\, \text{vol}_d(K)^{\frac{1}{d}},$$where $\xi^\perp$ is the hyperplane orthogonal to a unit vector $\xi$ .We show that  $C(d)$ can be chosen asymptotically of order $O(1)^d$ for hyperplane slices. Additionally, we will discuss some special cases and generalizations for this inequality.  This is a joint work with Martin Henk and Artem Zvavitch.
Friday, October 28, 2016 - 15:05 , Location: Skiles 005 , Sharath Raghvendra , Virginia Tech , Organizer: Esther Ezra
Motivated by real-time logistics, I will present a deterministic online algorithm for the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given a set S of server locations and a set R of request locations.The requests arrive one at a time and when it arrives, we must immediately and irrevocably match it to a free" server. The cost of matching a server to request is given by the distance between the two locations (which we assume satisfies triangle inequality). The objective of this problem is to come up with a matching of servers to requests which is competitive with respect to the minimum-cost matching of S and R.In this talk, I will show that this new deterministic algorithm performs optimally across different adversaries and metric spaces. In particular, I will show that this algorithm simultaneously achieves optimal performances in two well-known online models -- the adversarial and the random arrival models. Furthermore, the same algorithm also has an exponentially improved performance for the line metric resolving a long standing open question.
Friday, October 21, 2016 - 15:05 , Location: Skiles 005 , Esther Ezra , Georgia Tech , Organizer: Esther Ezra

Joint work with Micha Sharir (Tel-Aviv University).

Following a recent improvement of Cardinal etal. on the complexity of a linear decision tree for k-SUM, resulting in O(n^3 \log^3{n}) linear queries, we present a further improvement to O(n^2 \log^2{n}) such queries. Our approach exploits a point-location mechanism in arrangements of hyperplanes in high dimensions, and, in fact, brings a new view to such mechanisms. In this talk I will first present a background on the k-SUM problem, and then discuss bottom-vertex triangulation and vertical decomposition of arrangements of hyperplanes and how they serve our analysis.