| Date: | March 25th, 2019 |
|---|---|
| Speaker: | Cole Franks, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Three permutations, simplified |
| Abstract: | A k-permutation family on n vertices is a set system consisting of the intervals of k permutations of [n]. Both 1- and 2-permutation families have discrepancy 1, that is, one can color the vertices red and blue such that the number of reds and blues in each edge differs by at most one. That is, their discrepancy is bounded by one. Beck conjectured that the discrepancy of for 3-permutation families is also O(1), but Newman and Nikolov disproved this conjecture in 2011. We give a simpler proof that Newman and Nikolov's sequence of 3-permutation families has discrepancy at least logarithmic in n. We also exhibit a new, tight lower bound for the related notion of root-mean-squared discrepancy of a 6-permutation family. |
| Date: | March 11th, 2019 |
|---|---|
| Speaker: | Sophie Spirkl, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Detecting an odd hole |
| Abstract: | I will talk about a polynomial-time algorithm that decides whether a graph contains an induced cycle of odd length k > 3. Joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour. |
| Date: | February 25th, 2019 |
|---|---|
| Speaker: | Vishwas Bhargava, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Are factors of Sparse polynomials sparse? |
| Abstract: | The main question we will discuss is, how number of terms of a polynomial(a.k.a Sparsity) relates to number of terms of its factors. This is a fundamental problem which lies at the intersection of Algebra and Combinatorics and attracted attention from several authors, including Erdös, Freud, Rényi, Schinzel and Verdenius. We show a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular, we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s^{O({d^2\log{n}})}. This is the first nontrivial bound on factor sparsity for d >2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials. Joint work with Shubhangi Saraf and Ilya Volkovich. |
| Date: | February 18th, 2019 |
|---|---|
| Speaker: | Yufei Zhao, MIT |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | A Reverse Sidorenko Inequality |
| Abstract: | We prove a number of tight graph homomorphism inequalities, where, for a fixed H, we wish to maximize the number of homomorphism
from G to H (after exponentially normalizing by the size of G) under
certain degree constraints on G (e.g., d-regular). A highlight of our
results is that, among d-regular graphs of the same size, a disjoint
complete bipartite graphs has the most number of proper q-colorings. Our
results also extend to irregular graphs and list colorings. These
results settle a number of conjectures by Kahn, Galvin-Tetali, Galvin,
and Cohen-Csikvári-Perkins-Tetali. Joint work with Ashwin Sah, Mehtaab Sawhney, and David Stoner |
| Date: | February 11th, 2019 |
|---|---|
| Speaker: | Andrei Deneanu, Yale |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The probability that a matrix with Rademacher entries is normal |
| Abstract: | We consider a random nxn matrix, M_n, whose entries are independent and identically distributed (i.i.d.) Rademacher random variables (taking values {-1,1} with probability 1/2) and prove 2^{-(0.5+o(1))n^2} <=P (M_n is normal) <= 2^{-(0.302+o(1))n^{2}}. We conjecture that the lower bound is sharp. |
| Date: | February 4th, 2019 |
|---|---|
| Speaker: | Guy Moshkovitz, IAS |
| Time: | 2:00 |
| Place: | Hill Center 425 |
| Title: | A Tight Bound for Hypergraph Regularity |
| Abstract: | The hypergraph regularity lemma — the extension of Szemeredi’s graph regularity lemma to the setting of k-graphs — is one of the most celebrated combinatorial results obtained in the past decade. By now there are various (very different) proofs of this lemma, obtained by Gowers, Rodl, et al. and Tao. Unfortunately, what all these proofs have in common is that they yield partitions whose order is given by the k-th Ackermann function. We prove that such Ackermann-type bounds are unavoidable for every k>=2, thus confirming a prediction of Tao. |
| Date: | January 28th, 2019 |
|---|---|
| Speaker: | Lionel Levine, Cornell University |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | CoEulerian Graphs |
| Abstract: | In joint work with Matt Farrell, http://arxiv.org/abs/1502.04690 we suggest a measure of "Eulerianness" of a finite directed graph, and define a class of "coEulerian" graphs. These are the strongly connected graphs whose Laplacian lattice is as large as possible. As an application, we address a problem posed by Bjorner, Lovasz, and Shor in 1991. They asked how to tell if a given chip-firing game will be finite or infinite. Bjorner and Lovasz gave a decision procedure in 1992, which takes exponential time in the worst case. We show this can be improved to linear time (!) if the graph is coEulerian. A recent theorem of Nguyen and Wood, confirming a conjecture of Koplewitz, shows that coEulerian graphs are not rare: The directed random graph G(n,p) is coEulerian with limiting probability 1/(zeta(2)*zeta(3)*zeta(4)*...). So (in case you were wondering) about 43.58% of all simple directed graphs are coEulerian. |
| Date: | December 3rd, 2018 |
|---|---|
| Speaker: | Afonso Bandeira, NYU |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Optimization of random functions over the Hypercube |
| Abstract: | N/A |
| Date: | November 26th, 2018 |
|---|---|
| Speaker: | Mathias Schacht, Yale |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Powers of Hamiltonian cycles in randomly augmented graphs |
| Abstract: | We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every $k$ and sufficiently large $n$ already the minimum degree $\geq \frac{k}{k-1}n$ for an $n$-vertex graph $G$ alone suffices to ensure the existence of a $k$-th power of a Hamiltonian cycle. We show that under essentially the same degree assumption the addition of just $O(n)$ random edges ensures the presence of the $(k+1)$-st power of a Hamiltonian cycle with probability close to one. |
| Date: | November 19th, 2018 |
|---|---|
| Speaker: | Gal Kronenberg, Tel Aviv |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The chromatic index of random multigraphs |
| Abstract: | For a (multi)graph G=(V,E), we denote by χ'(G) the minimum number of colors needed to color the edges of G properly. Clearly, Δ≤χ'(G). Vizing proved that χ'(G)≤ Δ(G)+μ(G), where μ(G) is the maximum edge multiplicity of G. Let S⊆V and let ρ(G)=max{ e(S)/ \floor{|S|/2} | S⊆V }. By the fact that every color class forms a matching, we have that χ'(G)≥ρ(G). In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph G, χ'(G)ϵ{Δ, Δ+1,ρ(G)}. We show that their conjecture (in a stronger form) is true for random multigraphs. Let M(n,m) be the collection of all multigraphs with n vertices and m edges. Our result states that, for a given m:=m(n), almost all multigraphs in M(n,m) satisfy χ'(G)=max{Δ,ρ(G)}. In particular, we show that if n is even and m:=m(n), then χ'(M)=Δ(M) for a typical M~M(n,m). Furthermore, for a fixed ε >0, if n is odd, then a typical M~M(n,m) has χ'(M)=Δ for m≤(1- ε)n^3\log n, and for m≥(1+ ε)n^3\log n, a typical M~M(n,m) has χ'(M)=ρ(M). Joint work with Penny Haxell and Michael Krivelevich. |
| Date: | November 12th, 2018 |
|---|---|
| Speaker: | Ross Berkowitz, Yale |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Local Limit Theorems on Random Graphs |
| Abstract: | What is the probability that a random graph has exactly the average number of copies of $K_5$? We will discuss a new technique developed since our last talk at Rutgers for analyzing the characteristic functions of low degree polynomials over $G(n,p)$. This will allow us to prove local limit theorems for cliques of any fixed size in $G(n,1/2)$. |
| Date: | November 5th, 2018 |
|---|---|
| Speaker: | Wojtek Samotij, Tel Aviv |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The upper tail for triangles in sparse random graphs |
| Abstract: | Let X denote the number of triangles in the random graph G(n, p). The problem of determining the asymptotics of the rate of the upper tail of X, that is, the function f_c(n,p) = log Pr(X > (1+c)E[X]), has attracted considerable attention of both the combinatorics and the probability communities. We shall present a proof of the fact that whenever log(n)/n << p << 1, then f_c(n,p) = (r(c)+o(1)) n^2 p^2 log(p) for an explicit function r(c). This is joint work with Matan Harel and Frank Mousset. |
| Date: | October 29th, 2018 |
|---|---|
| Speaker: | Huseyin Acan, Drexel |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Bootstrap percolation on uniform attachment graphs |
| Abstract: | Bootstrap percolation is a process defined on a graph, which starts with a set S of initially infected vertices. Afterward, at each step, an uninfected vertex with at least r infected neighbors becomes infected and stays infected forever. If r=1, then all vertices in a connected graph get infected at some point as long as there is at least one infected vertex initially. However, for r>1, the final set of infected vertices depends on the graph and S. We study bootstrap percolation on a uniform attachment graph, which is a random graph on the vertex set [n], where each vertex v makes k selections from [v-1] uniformly and independently, and these selections determine the edge set. We start the process with a random S and find a threshold value of |S| for the spread of infection to all vertices. Joint work with Boris Pittel. |
| Date: | October 22nd, 2018 |
|---|---|
| Speaker: | Phil Wood, Wisconsin |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Limiting eigenvalue distribution for the non-backtracking matrix of an Erdos-Renyi random graph |
| Abstract: | A non-backtracking random walk on a graph is a directed walk with the constraint that the last edge crossed may not be immediately crossed again in the opposite direction. This talk will give a precise description of the eigenvalues of the adjacency matrix for the non-backtracking walk when the underlying graph is an Erdos-Renyi random graph on n vertices, where each edge is present independently with probability p. We allow p to be constant or decreasing with n, so long as p*sqrt(n) tends to infinity. The key ideas in the proof are partial derandomization, applying the Tao-Vu Replacement Principle in a novel context, and showing that partial derandomization may be interpreted as a perturbation, allowing one to apply the Bauer-Fike Theorem. Joint work with Ke Wang at HKUST (Hong Kong University of Science and Technology). |
| Date: | October 15th, 2018 |
|---|---|
| Speaker: | Sivakanth Gopi, Microsoft Research |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Locally decodable codes and arithmetic progressions in random settings |
| Abstract: | (1) A set D of natural numbers is called t-intersective if every positive upper density subset A of natural numbers contains a (t+1)-length arithmetic progression (AP) whose common differences is in D. Szemeredi's theorem states that the set of all natural numbers is t-intersective for every t. But there are other non-trivial examples like {p-1: p prime}, {1^k,2^k,3^k,\dots} for any k etc. which are t-intersective for every t. A natural question to study is at what density random subsets of natural numbers become t-intersective? (2) Let X_t be the number of t-APs in a random subset of Z/NZ where each element is selected with probability p independently. Can we prove precise estimates on the probability that X_t is much larger than its expectation? (3) Locally decodable codes (LDCs) are error correcting codes which allow ultra fast decoding of any message bit from a corrupted encoding of the message. What is the smallest encoding length of such codes? These seemingly unrelated problems can be addressed by studying the Gaussian width of images of low degree polynomial mappings, which seems to be a fundamental tool applicable to many such problems. Adapting ideas from existing LDC lower bounds, we can prove a general bound on Gaussian width of such sets which reproves the known LDC lower bounds and also implies new bounds for the above mentioned problems. Our bounds are still far from conjectured bounds which suggests that there is plenty of room for improvement. If time permits, we will discuss connections to type constants of injective tensor products of Banach spaces (or chernoff bounds for tensors in simpler terms). |
| Date: | October 8th, 2018 |
|---|---|
| Speaker: | Clara Shikhelman, Tel Aviv |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Generalized Turan-type problems for random graphs. |
| Abstract: | For two fixed graphs $T$ and $H$, a positive integer $n$ and a real number $p \in [0,1]$ let $ex(G(n,p),T,H)$ be the random variable counting the maximum number of copies of $T$ in an $H$-free subgraph of the random graph $G(n,p)$. In this talk we discuss this variable, its phase transition as a function of $p$ and its connection to the deterministic function counting the maximum number of copies of $T$ in an $H$-free graph on $n$ vertices. Based on joint works with N. Alon, A. Kostochka and W. Samotij. |
| Date: | October 1st, 2018 |
|---|---|
| Speaker: | Jinyoung Park, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The number of 4-colorings of the Hamming cube |
| Abstract: | Let $Q_d$ be the $d$-dimensional Hamming cube (hypercube) and $N=2^d$. We discuss the number of proper (vertex) colorings of $Q_d$ given $q$ colors. It is easy to see that there are exactly 2 of 2-colorings, but for $q >2$, the number of $q$-colorings of $Q_d$ is highly nontrivial. Since Galvin (2002) proved that the number of 3-colorings is asymptotically $6e2^{N/2}$, the other cases remained open so far. In this talk, we prove that the number of 4-colorings of $Q_d$ is asymptotically $6e2^N$, as was conjectured by Engbers and Galvin in 2012. The proof uses a combination of information theory (entropy) and isoperimetric ideas originating in work of Sapozhenko in the 1980's. This is joint work with Jeff Kahn. |
| Date: | September 24th, 2018 |
|---|---|
| Speaker: | Imre Leader, Cambridge |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Decomposing the complete r-graph |
| Abstract: | The Graham-Pollak theorem states that, if we wish to decompose the complete graph on n vertices into complete bipartite subgraphs, we need at least n-1. What happens for hypergraphs? We will present background and also some recent results. This is joint work with Luka Milicevic and Ta Sheng Tan. |
| Date: | September 17th, 2018 |
|---|---|
| Speaker: | Julian Sahasrabudhe, Cambridge |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | On a Problem of Littlewood : Counting Zeros of Cosine Polynomials |
| Abstract: | Click here for the abstract. |
| Date: | September 10th, 2018 |
|---|---|
| Speaker: | Sophie Spirkl, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Trees and linear anticomplete sets |
| Abstract: | For which graphs H is it true that there is an epsilon > 0 such that for all n > 1, and for every n-vertex graph G that does not contain H as an induced subgraph, either G has a vertex of degree at least epsilon n, or G contains two disjoint vertex sets A, B with |A|, |B| >= epsilon n, and there is no edge between A and B in G? Liebenau and Pilipczuk conjectured that this is true if H is a forest. I will talk about a proof of this conjecture, connections to the Erdos-Hajnal conjecture, and related questions. Joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour. |
| Date: | April 30th, 2018 |
|---|---|
| Speaker: | Sebastian Cioaba, U. Delaware |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The smallest eigenvalues of some Hamming and Johnson graphs |
| Abstract: | The smallest eigenvalue of a graph is closely related to other graph parameters such as the independence number, the chromatic number or the max-cut. In this talk, I will describe some of the connections between the smallest eigenvalue and the max-cut of a graph that have motivated various researchers such as Karloff, Alon, Sudakov, Van Dam, Sotirov to investigate the smallest eigenvalue of Hamming and Johnson graphs. I will outline our proofs of a 2016 conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a 1999 conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs and mention some open problems. This is joint work with Andries Brouwer, Ferdinand Ihringer and Matt McGinnis. |
| Date: | April 23rd, 2018 |
|---|---|
| Speaker: | Shay Moran, IAS |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | On the expressiveness of comparison queries |
| Abstract: | Comparisons are a classical and well studied algorithmic tool that is used in a variety of contexts and applications. We will discuss two manifestations of the expressiveness of these queries in machine learning and complexity theory (a more detailed overview is given below). Both manifestations are based on the notion of "inference dimension” that can be viewed as another instance of the fruitful link between machine learning and discrete mathematics - a link dating back to the discovery of the VC dimension. 1) Active classification with comparison queries [Kane, Lovett, Moran, Zhang ’17] Active learning is a model for semi-supervised learning that captures situations in which unlabeled data is abundant and manually labelling it is expensive. We consider an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a specific restaurant (a label query); or which one of two restaurants did she like more (a comparison query). We prove that the usage of comparison queries leads to an exponential improvement in the query complexity of some well studied problems. Specifically, for the class of half-spaces, we show that under natural assumptions, such as large margin or bounded bit-description of the input examples, it is possible to reveal all the labels of a sample of size n using approximately O(logn) queries. 2) Nearly optimal linear decision trees for k-SUM and related problems [Kane, Lovett, Moran ’17] We use the above framework to construct linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant k, we construct linear decision trees that solve the k-SUM problem on n elements using O(n log n) linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two k-subsets; when viewed as linear queries, comparison queries are 2k-sparse and have only {-1,+1} coefficients. We give similar constructions for sorting sumsets A+B and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms. |
| Date: | April 16th, 2018 |
|---|---|
| Speaker: | Yufei Zhao, MIT |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Tower-type bounds for Roth's theorem with popular differences |
| Abstract: | A famous theorem of Roth states that for any $\alpha > 0$ and $n$ sufficiently large in terms of $\alpha$, any subset of $\{1, \dots, n\}$ with density $\alpha$ contains a 3-term arithmetic progression. Green developed an arithmetic regularity lemma and used it to prove that not only is there one arithmetic progression, but in fact there is some integer $d > 0$ for which the density of 3-term arithmetic progressions with common difference $d$ is at least roughly what is expected in a random set with density $\alpha$. That is, for every $\epsilon > 0$, there is some $n(\epsilon)$ such that for all $n > n(\epsilon)$ and any subset $A$ of $\{1, \dots, n\}$ with density $\alpha$, there is some integer $d > 0$ for which the number of 3-term arithmetic progressions in $A$ with common difference $d$ is at least $(\alpha^3-\epsilon)n$. We prove that $n(\epsilon)$ grows as an exponential tower of 2's of height on the order of $\log(1/\epsilon)$. We show that the same is true in any abelian group of odd order $n$. These results are the first applications of regularity lemmas for which the tower-type bounds are shown to be necessary. Joint work with Jacob Fox and Huy Tuan Pham. |
| Date: | April 9th, 2018 |
|---|---|
| Speaker: | Thomas Lidbetter, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Games of Hide-and-seek with Balls in Boxes |
| Abstract: | We consider zero-sum games in which one player (the Hider) hides k balls among n boxes and the other player (the Searcher) inspects the boxes one by one until finding all k balls. The Searcher has to pay a cost to inspect each box, and may or may not be limited to finding at most one ball each time she inspects a box. We may consider two different objectives for the Searcher: to minimize the total cost incurred in finding all the balls, or to minimize her regret, which is the total cost minus what she'd pay if she knew where all the balls were. We seek optimal (min-max) solutions for both players. No knowledge of game theory will be assumed - the fundamentals of zero-sum games will be explained. |
| Date: | April 2nd, 2018 |
|---|---|
| Speaker: | Aditya Potukuchi, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | On the hardness of coloring rainbow-colorable hypergraphs |
| Abstract: | A (uniform) hypergraph is c-colorable if its vertices can be assigned colors from 1,...,c so that no hyperedge is monochromatic. A hypergraph is r-rainbow colorable (or r-polychromatic) if its vertices can be assigned colors from 1,...,r so that every edge has all r colors. It is very easy to see that if a hypergraph is r-rainbow colorable for r \geq 2, then it is 2-colorable. However, given a hypergraph with the promise that is r-rainbow colorable for r \geq 2, finding an efficient algorithm that outputs a proper 2-coloring of it does not always seem to be an easy problem. This result shows that finding a c-coloring of a k-uniform, k(1 - o_c(1))-rainbow colorable hypergraph is NP-hard. The gadgets involved in the reduction are some kinds of variations/generalizations of the Kneser hypergraph, some of which seem to be well studied, and some which are not (as far as we know). This is based on joint work with Per Austrin and Amey Bhangale. |
| Date: | March 26th, 2018 |
|---|---|
| Speaker: | Eyal Lubetzky, NYU |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Asymptotics in bond percolation on expanders |
| Abstract: | We consider supercritical bond percolation on a family of high-girth $d$-regular expanders. Alon, Benjamini and Stacey (2004) established that its critical probability for the appearance of a linear-sized (``giant'') component is $p_c=1/(d-1)$. Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant at any $p>p_c$, as well as that of its 2-core. It was further shown in [ABS04] that the second largest component, at any $0 < p < 1$, has size at most $n^{\omega}$ for some $\omega<1$. We show that, unlike the situation in the classical Erd\H{o}s--R\'enyi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size $n^{\omega'}$ for $\omega'$ arbitrarily close to $1$. Moreover, as a by-product of that construction, we answer negatively a question of Benjamini (2013) on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, e.g., the existence of a linear path. Joint work with M. Krivelevich and B. Sudakov. |
| Date: | March 19th, 2018 |
|---|---|
| Speaker: | Henry Towsner, Penn |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Hypergraphs and higher dimension analogs of VC dimension |
| Abstract: | The notion of bounded VC dimension is a property at the intersection of combinatorics and probability. This family has been discovered repeatedly and studied from various perspectives - for instance, in model theory, theories with bounded VC dimension are known as NIP (the theories which do Not have the Independence Property). One useful property is that graphs with bounded VC dimension are the graphs that can be always be finitely approximated in a "random-free" way: graphs with bounded VC dimension satisfy a strengthening of Szemeredi's Regularity Lemma in which the densities between the pieces of the partition are either close to 0 or close to 1. The generalization of VC dimension to higher arity, known in model theory as k-NIP for various k, has been less well-studied. We summarize some known facts about this generalization, including a new result (joint with Chernikov) showing k-NIP hypergraphs have a similar kind of random-free approximation. To define this notion cleanly, we will need to use a measure-theoretic approach to working with hypergraph regularity. |
| Date: | March 5th, 2018 |
|---|---|
| Speaker: | Oanh Nguyen, Princeton |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Universality of random functions |
| Abstract: | In this talk, we will discuss recent progress in the study of random functions with a focus on a general framework to prove some universality properties of the roots of random functions. We illustrate how to apply this framework to some popular models of random functions such as random Kac polynomials, random trigonometric polynomials, random Taylor series, and so on. This is joint work with Van Vu. |
| Date: | February 26th, 2018 |
|---|---|
| Speaker: | Noga Alon, Princeton and Tel Aviv University |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Cayley graphs and list-decodable zero-rate codes |
| Abstract: | What is the maximum possible number of words in a binary code of length n so that there is no Hamming ball of radius (1/4+epsilon)n containing more than two words ? I will show that the answer is Theta(1/epsilon^{3/2}). A crucial ingredient in the proof is a construction of a family of Cayley graphs which is useful in tackling several additional extremal problems in Graph Theory and Geometry. Joint work with Bukh and Polyanskiy. |
| Date: | February 19th, 2018 |
|---|---|
| Speaker: | Paul Seymour, Princeton |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Gyarfas-Sumner meets Erdos-Hajnal |
| Abstract: | The Gyarfas-Sumner conjecture says that every graph with huge (enough) chromatic number and bounded clique number contains any given forest as an induced subgraph. The Erdos-Hajnal conjecture says that for every graph H, all graphs not containing H as an induced subgraph have a clique or stable set of polynomial size. This talk is about a third problem related to both of these, the following. Say an n-vertex graph is "c-coherent'' if every vertex has degree < cn, and every two disjoint vertex subsets of size at least cn have an edge between them. To prove a given graph H satisfies the Erdos-Hajnal conjecture, it is enough to prove H satisfies the conjecture in all c-coherent graphs and their complements, where c>0 is fixed and as small as we like. But for some graphs H, all c-coherent graphs contain H if c is small enough, so half of the task is done for free. Which graphs H have this property? Paths do (a theorem of Bousquet, Lagoutte, and Thomasse), and non-forests don't. Maybe all forests do? In other words, do all c-coherent graphs with c small enough contain any given forest as an induced subgraph? That question is the topic of the talk. It looks much like the Gyarfas-Sumner conjecture, but it seems easier, and there are already several pretty results. For instance the conjecture is true for all subdivided caterpillars (which is more than we know for Gyarfas-Sumner), and all trees of radius two. Joint work with Maria Chudnovsky, Anita Liebenau, Marcin Pilipczuk, Alex Scott and Sophie Spirkl. |
| Date: | February 12th, 2018 |
|---|---|
| Speaker: | Adam Marcus, Princeton |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Using rectangular convolutions to construct biregular expanders |
| Abstract: | I will discuss recent advances in the technique we call "the method of interlacing polynomials'' --- a technique that uses polynomials as a way to prove existence theorems in linear algebra. Previous results used this method to show the existence of bipartite Ramanujan graphs of any size and degree, and subsequent progress was made in the work of Cohen in the form of a polynomial time construction. This talk will discuss some recent progress in extending these results to the case of biregular, bipartite expanders. Unlike classical Ramanujan graphs, these new constructions can have partitions of different sizes, making them more suitable for many applications. This is joint work with Aurelien Gribinski. |
| Date: | January 29th, 2018 |
|---|---|
| Speaker: | Keith Frankston, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | On regular 3-wise intersecting families |
| Abstract: | Ellis and Narayanan showed, verifying a conjecture of Frankl, that any 3-wise intersecting family of subsets of {1,2,...,n} admitting a transitive automorphism group has cardinality o(2^n), while a construction of Frankl demonstrates that the same conclusion need not hold under the weaker constraint of being regular. Answering a question of Cameron, Frankl and Kantor from 1989, we show that the restriction of admitting a transitive automorphism group may be relaxed significantly: we prove that any 3-wise intersecting family of subsets of {1,2,...,n} that is regular and increasing has cardinality o(2^n). |
| Date: | January 22nd, 2018 |
|---|---|
| Speaker: | Reza Gheissari, NYU |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Local MINCUTs and the Ising model on Dense Random Graphs |
| Abstract: | Consider a dense Erdos--Renyi random graph $G(n,p)$ with $p>0$ fixed. Can we partition the graph into two nonempty sets such that every vertex has more neighbors in its own set than in the other? Will a "greedy search" algorithm find such local MINCUTs or will it end up in one of the two trivial partitions $([n],\emptyset)$? We relate these two questions to the local energy minima of an Ising model on the random graph. While we leave open the question of whether/how many nontrivial local minima exist, one might expect that as in similar disordered systems, there are a rapidly diverging (in $n$) number of such local minima. We prove, however, that starting from a typical initial configuration, a dynamic search for local minima avoids all such local minima with high probability and quickly ends up in one of the two homogenous ground states (corresponding to the two trivial partitions). |
| Date: | November 27th, 2017 |
|---|---|
| Speaker: | Jozsef Skokan, London School of Economics |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The Multicolour Ramsey Number of a Long Odd Cycle. |
| Abstract: | Click here for the abstract. |
| Date: | November 20th, 2017 |
|---|---|
| Speaker: | Jozsef Beck, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Combinatorics and equidistribution of geodesics on flat surfaces |
| Abstract: | A Cubeline means a geodesic on the cube surface. What can we say about the equidistribution of a concrete Cubeline with given slope, say slope square-root-2? What about the equidistribution of billiards in a nontrivial polyomino, say the L-shaped one (3 unit squares)? How does combinatorics enter the story? We attempt to answer these questions. |
| Date: | November 13th, 2017 |
|---|---|
| Speaker: | Evita Nestoridi, Princeton |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Cutoff for random to random |
| Abstract: | Random to random is a card shuffling model that was created to study strong stationary times. Although the mixing time of random to random has been known to be of order nlogn since 2002, cutoff had been an open question for many years, and a strong stationary time giving the correct order for the mixing time is still not known. In joint work with Megan Bernstein, we use the eigenvalues of the random to random card shuffling to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4(nlogn), answering a conjecture of Diaconis. |
| Date: | November 6th, 2017 |
|---|---|
| Speaker: | Greta Panova, UPenn/IAS |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Hook formulas for skew shapes: combinatorics, asymptotics and beyond |
| Abstract: | The celebrated hook-length formula of Frame, Robinson and Thrall from 1954 gives a product formula for the number of standard Young tableaux of straight shape. No such product formula exists for skew shapes. In 2014, Naruse announced a formula for skew shapes as a positive sum of products of hook-lengths using "excited diagrams" [ Ikeda-Naruse, Kreiman, Knutson-Miller-Yong] coming from Schubert calculus. We will show combinatorial and aglebraic proofs of this formula, leading to a bijection between SSYTs or reverse plane partitions of skew shape and certain integer arrays that gives two q-analogues of the formula. We will also show how these formulas can be proven via non-intersecting lattice paths interpretations, and show various applications connecting Dyck paths and alternating permutations. We show how excited diagrams give asymptotic results for the number of skew Standard Young Tableaux in various regimes of convergence for both partitions. We will also show a multivariate versions of the hook formula with consequences to exact product formulas for certain skew SYTs and lozenge tilings with multivariate weights. Joint work with A. Morales and I. Pak. |
| Date: | October 30th, 2017 |
|---|---|
| Speaker: | Deepak Bal, Montclair State |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Monochromatic Components in Random Graphs |
| Abstract: | We are concerned with the following Ramsey-type question: if the edges of a graph G are r-colored (not necessarily properly), what is the largest monochromatic component (or path, or cycle) which must appear? We may also ask for a cover or a partition of the vertex set of G by few monochromatic pieces. We discuss some recent work addressing these questions when G is a random graph. This is joint work with Michael Anastos and Louis DeBiasio. |
| Date: | October 23rd, 2017 |
|---|---|
| Speaker: | Sophie Spirkl, Princeton |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The structure of triangle-free graphs with no induced six-vertex path |
| Abstract: | I will talk about an explicit construction for triangle-free graphs that do not contain a six-vertex path as an induced subgraph. Examples include the 16-vertex Clebsch graph, and the graph that arises from a complete bipartite graph by subdividing every edge of a perfect matching exactly once. We show that every connected triangle-free graph with no six-vertex induced path can be obtained from an induced subgraph of one of these two by restricted homogeneous set and homogeneous pair operations. Joint work with Maria Chudnovsky, Paul Seymour, and Mingxian Zhong. |
| Date: | October 16th, 2017 |
|---|---|
| Speaker: | Swastik Kopparty, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Approximate affine invariance and distance to polynomials |
| Abstract: | Let F be a finite field, and let V be the set of functions from F to F computed by a univariate polynomial of degree at most d. It is easy to see that V is closed under affine transformations: i.e., if g(X) is in V, then so is h(X) = g(aX+b). V is also closed under taking linear combinations. We will study what happens to functions *not in V* when we apply random affine transformations and take random linear combinations of these. Our main result is that these operations increase the distance to V very quickly. Joint work with Eli Ben-Sasson and Shubhangi Saraf |
| Date: | October 9th, 2017 |
|---|---|
| Speaker: | Noah Stephens-Davidowitz, Princeton/IAS |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | A Reverse Minkowski Theorem |
| Abstract: | A classical problem in the geometry of numbers asks us to estimate how many lattice points lie in some ball around the origin. Minkowski’s celebrated theorem gives us a tight lower bound for this number that depends only on the determinant of the lattice. (One can think of the determinant as the limit of the density of lattice points inside large balls--i.e., the "global density" of the lattice. So, Minkowski’s theorem gives a lower bound on a lattice’s “local density” based on its “global density.”) We resolve a conjecture due to Dadush that gives a nearly tight converse to Minkowski’s theorem—an upper bound on the number of lattice points in a ball that depends only on the determinants of sublattices. This theorem has numerous applications, from complexity theory, to the geometry of numbers, to the behavior of Brownian motion on flat tori. Based on joint work with Oded Regev. |
| Date: | October 2nd, 2017 |
|---|---|
| Speaker: | Chun-Hung Liu, Princeton |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | The Erdos-Posa property |
| Abstract: | For a family F of graphs, the packing number p of a graph G for F is the maximum size of a collection of pairwise disjoint subgraphs of G where each isomorphic to a member of F; the covering number c of G for F is the minimum size of a subset of vertices of G intersecting all subgraphs of G isomorphic to members of F. We say F has the Erdos-Posa property if there exists a function f such that c is at most f(p) for every graph G. Robertson and Seymour proved that if F is the set of H minors for some graph H, then F has the Erdos-Posa property if and only if H is planar. In this talk I will provide a complete but complicated characterization for the graphs H such that the set of H subdivisions has the Erdos-Posa property, and show that it is NP-hard to decide whether the input graph H has this property, so that the complication of the characterization is unlikely to be avoidable. This is joint work with Luke Postle and Paul Wollan and answers a question of Robertson and Seymour. Then I will discuss how to simplify the characterization by relaxing the conditions for having the Erdos-Posa property. In particular, I will show that for every graph H, the set of H subdivisions always has the Erdos-Posa property if we allow the packing to be half-integral. This statement easily implies a conjecture of Thomas. |
| Date: | September 25th, 2017 |
|---|---|
| Speaker: | Ron Aharoni, Technion |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Cooperative colorings |
| Abstract: | Given graphs $G_1, \ldots, G_k$ on the same vertex set $V$, a {\em cooperative coloring} is a choice of an independent set $I_j$ in each $G_j$, such that $\bigcup_{j \le k}I_j=V$. When all $G_i$s are the same graph, this is the familiar notion of $k$-coloring. What is the analogue of the fact that the coloring number of a graph $G$ is no larger than $\Delta(G)+1$? A sample result: three cycles have a cooperative coloring. Joint works with Berger, Chudnovsky, Holzman, Jiang and Spr\"ussel. |
| Date: | September 18th, 2017 |
|---|---|
| Speaker: | Imre Leader, University of Cambridge |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Tiling with Arbitrary Tiles |
| Abstract: | It is easy to tile the plane with dominoes (2x1 rectangles). It is also easy to tile the plane with trominoes (three 1x1 squares forming an L-shape). Of course, not every shape tiles the plane. What happens when we increase the number of dimensions from two to three, or beyond? |
| Date: | September 11th, 2017 |
|---|---|
| Speaker: | Bhargav Narayanan, Rutgers |
| Time: | 2:00 |
| Place: | Hill Center 705 |
| Title: | Diffusion on Graphs |
| Abstract: | Diffusion on a graph G is a cellular automaton describing how integer labels on the vertices of G evolve. We view the label of a vertex as the number of chips at that vertex, and at each step, each vertex simultaneously sends one chip to each of its neighbours with fewer chips. What can we say about the trajectories of various initial configurations in this process? Here’s an amuse bouche: this firing rule may generate negative labels when started from a completely positive initial configuration, so it is not clear, a priori, if one must even have periodic behaviour necessarily! |