Abstracts

Fractional matchings and covers in families of (weighted) d-intervals
Shira Zerbib, Technion

Abstract: A $d$-interval hypergraph consists of edges that are each the union of $d$ closed intervals on the real line. Kaiser showed that the ratio between the covering number and the matching number in such hypergraphs is bounded by $d^2-d+1$. I will present some new results regarding the weighted and fractional versions of this theorem, and examples for their sharpness. To this end I will describe a weighted version of Tur\'{a}n's theorem. I will also discuss an extension of the KKM theorem (due to Shapley) and use it to give a straightforward proof to Kaiser's theorem.

Joint work with R. Aharoni and T. Kaiser.

Back

On the influences of low degree bounded functions
Noam Lifshitz, Bar-Ilan University

Abstract: The influence of the $k$-th coordinate on a Boolean function $f$ measures how likely is $f(x)$ to change when the $k$-th coordinate of $x$ is flipped while the other coordinates remain unchanged. Influences were studied extensively in the last 25 years, and they have applications to theoretical computer science, mathematical physics, and various other fields.

In this talk we consider bounded functions on the discrete cube, i.e., $f:{-1,1}^n -> [-1,1]$. In this case, one of the natural definitions of influence is the $L_1$ influence, defined as $I_k(f)=E[ |f(x)-f(x+e_k)| ]$. We study the following question, raised by Aaronson and Ambainis in the context of quantum computation. Assume that $f$ has degree $d$ as a multilinear polynomial. Is it true that the sum of $L_1$ influences of $f$ can be bounded as a function of $d$ (independent of $n$)?

In a recent paper, Backurs and Bavarian showed an upper bound of $O(d^3)$ for general functions and $O(d^2)$ for homogeneous functions. We improve the upper bounds to $d^2$ for general functions and $O(d \log d)$ for homogeneous functions. Furthermore, we present an upper bound of $d / 2\pi$ for monotone functions and show that it is tight. Our proofs use tools from approximation theory, such as Bernstein-Markov type inequalities.

Joint work with Yuval Filmus (IAS), Hamed Hatami (McGill), and Nathan Keller.

Back

The local theory of tournaments
Avraham Morgenstern, Hebrew University

Abstract: The Erd\H{o}s-Hajnal conjecture states that for every graph H there exists an injection of H into G for every large graph G whose largest homogeneous subset (clique or anti-clique) is sub-polynomial in |G|. We formulate a local version of this conjecture, and prove it for all 3-vertex graphs H. We prove the tournament analog for all 4-vertex tournaments H. We initiate the study of the 4-local profiles of tournaments, and derive some bounds on these sets. In particular, given the number of cycles of length 3, which tournaments minimize the number of cycles of length 4? Given the number of transitive triangles, which tournaments minimize the number of transitive quadruples? We state a conjecture, and derive an almost matching bound. We show that these two questions are equivalent, and describe some related questions. For example: Can the cyclic triangles be uniformly distributed along the edges of a large tournament? (answer: No, except for trivial cases).

Joint Work with Nati Linial.

Back

Triangles in H-free graphs
Clara Shikhelman, Tel-Aviv University

Abstract: For two graphs T and H and an integer n, let ex(n, T, H) denote the maximum possible number of copies of T in an H-free graph on n vertices. The study of this function when T = K_2 (a single edge) is one of the main subjects of extremal graph theory. We investigate the general function, focusing on the case T = K_3, which reveals several interesting phenomena.

In this talk we will present proofs of the following main results:
(i) For any fixed s > 1 and t > (s-1) one has ex(n,K_3,K_{s,t})=\Theta(n^{3-3/s}), and
(ii) ex(n,K_3,C_5) < (1+o(1)) (\sqrt 3)/2 n^{3/2}.

The last statement improves (slightly) a result of Bollobas and Gyori.

Joint work with Noga Alon.

Back

On the phase transition in random simplicial complexes
Yuval Peled, Hebrew University

Abstract: It is well-known that the G(n,p) model of random graphs undergoes a dramatic change around p=1/n. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant connected component. Several years ago, Linial and Meshulam have introduced the X_d(n,p) model, a probability space of n-vertex d-dimensional simplicial complexes, where X_1(n,p) coincides with G(n,p). Within this model we prove a natural d-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real d-th homology of complexes from X_d(n,p), and show that it is strictly greater than the threshold of d-collapsibility. In addition, we compute the real Betti numbers, i.e. the dimension of the homology groups, of X_d(n,p) for p=c/n. Finally, we establish the emergence of giant shadow at this threshold. (For d=1 a giant shadow and a giant component are equivalent). Unlike the case for graphs, for d > 1 the emergence of the giant shadow is a first order phase transition.

The talk will contain the necessary toplogical background on simplicial complexes, and will focus on the main idea of the proof: the local weak limit of random simplicial complexes and its role in the analysis of phase transitions.

Joint work with Nati Linial.

Back

Matroids, log-concavity and measure concentration
Karim Adiprasito, IHES and Hebrew University

Abstract: We provide a simple proof of the Rota--Heron--Welsh conjecture for matroids realizable as c-arrangements in the sense of Goresky--MacPherson: we prove that the coefficients of the characteristic polynomial of the associated matroids form log-concave sequences, proving the conjecture for a family of matroids out of reach for all previous methods. To this end, we study the L\'evy--Milman measure concentration phenomenon on natural push-forwards of uniform measures on the Grassmannian to realization spaces of arrangements under a certain extension procedure on matroids.

Back

High dimensional expanders
Tali Kaufman, Bar-Ilan University

Abstract: Expander graphs have been intensively studied in the last four decades. In recent years a high dimensional theory of expanders has emerged. In this talk I will introduce the notion of high dimensional expanders and some of the motivations for studying them. As opposed to (1-dimensional) expanders, where a random bounded degree graph is an expander, a probabilistic construction of a bounded degree high dimensional expander is not known. A major open problem, formulated by Gromov, is whether *bounded degree* high dimensional expanders could exist for dimension d >= 2. I will discuss a recent construction of explicit bounded degree 2-dimensional expanders, that answer Gromov's question in the affirmative.

Joint work with David Kazhdan and Alexander Lubotzky.

Back

Arrangements of equal minors in the positive Grassmannian
Miriam Farber, MIT

Abstract: We discuss arrangements of equal minors in totally positive matrices. More precisely, we would like to investigate the structure of possible equalities and inequalities between the minors. We show that arrangements of equals minors of largest value are in bijection with sorted sets, which earlier appeared in the context of alcoved polytopes and Grobner bases. Maximal arrangements of this form correspond to simplices of the alcoved triangulation of the hypersimplex; and the number of such arrangements equals the Eulerian number. On the other hand, we conjecture and prove in many cases that arrangements of equal minors of smallest value are exactly the weakly separated sets. Weakly separated sets, originally introduced by Leclerc and Zelevinsky, are closely related to the positive Grassmannian and the associated cluster algebra.

This is a joint work with Alexander Postnikov.

Back

Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph
Chaya Keller, Hebrew University

Abstract:

Back

Sign rank, VC dimension and spectral gaps
Shay Moran, Technion

Abstract: We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe connections to combinatorics, communication complexity and learning theory.

We also provide explicit examples of matrices with low VC dimension and high sign rank. Let $A$ be the $N \times N$ point-hyperplane incidence matrix of a finite projective geometry with order $n \geq 3$ and dimension $d \geq 2$. The VC dimension of $A$ is $d$, and we prove that its sign rank is larger than $N^{\frac{1}{2}-\frac{1}{2d}}$. The large sign rank of $A$ demonstrates yet another difference between finite and real geometries.

To analyze the sign rank of $A$, we introduce a connection between sign rank and spectral gaps, which may be of independent interest. Consider the $N \times N$ adjacency matrix of a $\Delta$-regular graph with a second eigenvalue (in absolute value) $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. A similar statement holds for all regular (not necessarily symmetric) sign matrices. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.

Joint work with Noga Alon and Amir Yehudayoff.

Back