Organizers : Jeff Kahn, Bhargav Narayanan, and Abigail Raz

Date: December 3rd, 2018

Speaker: Afonso Bandeira, NYU

Title: Optimization of random functions over the Hypercube

Abstract: N/A

Date: November 26th, 2018

Speaker: Mathias Schacht, Yale

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

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

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

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

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

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

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

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

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

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

Title: On a Problem of Littlewood : Counting Zeros of Cosine Polynomials

Abstract: Click here

Date: September 10th, 2018

Speaker: Sophie Spirkl, Rutgers

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.