# Combinatorics

### Previous Lectures

A braided vector space is a pair $(V, \Psi)$, where $V$ is a vector space

and $\Psi: V \otimes V \to V \otimes V$ is an invertible linear operator

such that $\Psi_1 \Psi_2 \Psi_1 = \Psi_2 \Psi_1 \Psi_2$. Given a braided

vector space $(V, \Psi)$, we constructed a family of braided vector spaces

$(V, \Psi^{(\epsilon)})$, where $\epsilon$ is a bitransitive function. Here a

bitransitive function is a function $\epsilon: [n] \times [n] \to \{1, -1\}$ such

that both of $\{(i,j) : \epsilon(i,j) = 1\}$ and $\{(i,j) : \epsilon(i,j) = -1\}$ are

transitive relations on $[n]$. The braidings $\Psi^{(\epsilon)}$ are monomials.

Therefore we call them monomial braidings.

We generalized this construction to the case of multi-colors. Given a braided

vector space $(V, \Psi)$, we used C-transitive functions to parametrize the

braidings on $V^{\otimes n}$ which come from $\Psi_1, \ldots, \Psi_{n-1}$.

Since $[n] \times [n]$ can be viewed as the set of edges of the bi-directed

complete graph with n vertices, a C-transitive function $\epsilon: [n] \times [n] \to C$

can be view as a C-transitive function on a bi-directed complete graph.

We generalized the concept of C-transitive functions to C-transitive functions on

any directed graphs. We showed that the number |\Epsilon_G(C)| of all C-transitive

functions on a directed graph G is a polynomial in |C|. This is a new invariant in graph

theory. It is analogue to the chromatic polynomial for an undirected graph in graph theory.

This talk is based on joint work with Arkady Berenstein and Jacob Greenstein.

In this talk, we will present an asymptotically tight bound on the largest number of distinct projections onto \alpha n coordinates guaranteed in any family of n^r binary vectors of length n, where 0 < \alpha \le 1 and r = n^{o(1)}, thus closing a gap open since a work of Bollobas and Radcliffe from 1995. For the proof, we establish a “sparse” version of a classical result, the Kruskal-Katona Theorem, where we give a stronger guarantee when the hypergraph does not induce dense subhypergraphs. We also present a geometric application regarding point-halfspace separation in R^d.

The talk is based on a recent joint work with Noga Alon and Guy Moshkovitz.

We say that a partition is odd if its dimension (computed by the hook-length formula) is odd. It turns out that the number a(n) of odd partitions of a positive integer is always a power of 2. This was proven independently by Macdonald and McKay. We will show that the subposet of the Young lattice consisting of odd partitions is a binary tree, and give an explicit recursive characterisation of this tree.

We say that a partition is chiral if the associated irreducible representation composed with the determinant map gives the sign character. Denote the number of chiral partitions of n by b(n). L. Solomon first considered the problem of enumeration of b(n) and Stanley posed it as an open problem in his book. We solve this problem by giving an explicit formula for b(n). We also show that the enumerations of a(n) and b(n) are closely related. The primary tool in our solution is J. Olsson's theory of core towers.

This is joint work with A. Prasad and S. Spallone.

It has been known since work of Feynman in the 50s that the behaviour of quantum systems is related to cycles of random permutations,

and for some systems this can be made a precise mathematical claim. Similar problems appear in the, mostly recreational, field of card shuffling.

All these problems can be attacked by representation theory, but algebra alone is not enough, as the functions involved are not class functions.

This creates an exciting analytic-algebraic nexus which has seen lots of progress recently, which I will survey in the talk.

No prior knowledge of any of the topics will be assumed.

We express some open problems in graph theory in terms of Ihara graph zeta

functions, or, equivalently, non-backtracking matrices of graphs. We focus

on "expanders" and random regular graphs, but touch on some seemingly

unrelated problems encoded in zeta functions.

We suggest that zeta functions of sheaves on graphs may have relevance to

complexity theory and to questions of Stark and Terras regarding whether

coverings of a fixed graph can ramify like number field extensions.

This talk assumes only basic linear algebra and graph theory. Part of the

material is joint work with David Kohler and Doron Puder.

Back in 2005, Berenstein, Fomin and Zelevinsky discovered a cluster

structure in the ring of regular functions on a double Bruhat cell in a

semisimple Lie group, in particular, SL_n. This structure can be easily

extended to the whole group. The compatible Poisson bracket is given by

the standard r-matrix Poisson-Lie structure on SL_n. The latter is a

particular case of Poisson-Lie structures corresponding to

quasi-triangular Lie bialgebras. Such structures where classified in 1982

by Belavin and Drinfeld. In 2012, we have conjectured that each

Poisson-Lie structure on SL_n gives rise to a cluster structure, and gave

several examples of exotic cluster structures corresponding to Poisson-Lie

structures distinct from the standard one. In my talk I will tell about the

progress in the proof of this conjecture and its modifications.

Joint with M.Gekhtman and M.Shapiro.

A number of methods of the algebraic graph theory were influenced by the spectral theory of Riemann surfaces.

We pay it back, and take some classical results for graphs to the continuous setting. In particular, I will talk about colorings, average distance and discrete random walks on surfaces.

Based on joint works with E. DeCorte and A. Kamber.

A flip graph is a graph, on a set of objects, in which adjacency reflects local change.

Flip graphs, from different domains, have surprising common properties, in terms of algebraic, combinatorial and metric properties.

In particular, they carry similar group actions, are intimately related to posets and have similar diameter formulas.

In this work, we introduce a new family of flip graphs, the Yoke graphs, which generalizes several formerly considered graphs --

on triangulations, permutations and trees.

Our main result is the computation of the diameter of an arbitrary Yoke graph.

At the heart of the proof lies the idea of transforming a diameter evaluation to an eccentricity problem.

This work forms part of a PhD thesis written under the supervision of Ron Adin and Yuval Roichman.

The famous Kazhdan-Lusztig conjectures, formulated in the late 1970s and proved soon after independently by Beilinson-Bernstein and Brylinski-Kashiwara,

underscore a deep relationship between representation theory, combinatorics and geometry.

Recent progress in representation theory of the general linear group over p-adic fields led us to speculate a relationship between particular cases of parabolic Kazhdan-Lusztig polynomials

(which are certain alternating sums of ordinary ones) and ordinary ones. I will discuss what is known theoretically and some empirical results.

No prior familiarity with these concepts will be assumed.

Based on joint work with Alberto Minguez.

The classical Helly's theorem, dated 1923, asserts that if F is a family of compact convex sets in R^d such that any d+1 sets of F have a non-empty intersection, then all sets of F can be pierced by a single point. Helly's theorem is a cornerstone in convexity theory, and the need to generalize and extend it has led mathematicians to deep and fascinating new research directions. One of the best-known extensions is the Alon-Kleitman (p,q) theorem (1992) which asserts that for F as above, if among any p sets of F some q intersect (for q>d), then all sets of F can be pierced by a bounded number c(p,q,d) of points.

In this talk we survey the quest for *quantitative *Helly-type theorems which aim at finding effective bounds on the piercing numbers in various scenarios. We present new bounds on c(p,q,d) for the Alon-Kleitman theorem, which are almost tight for a wide range of parameters. We also show that for several large classes of families, quantitative (p,2) theorems in the plane can be obtained, providing a strong connection between the piercing number of a family to its well-studied packing number, and giving rise to new Ramsey-type theorems.

Based on joint works with Shakhar Smorodinsky and Gabor Tardos.

The block number of a permutation is the maximal number of components in its expression as a direct sum.

The distribution of the set of left-to-right maxima over 321-avoiding permutations with block number k is shown to be equal to

the distribution of this set over 321-avoiding permutations with the last descent of the inverse permutation at position n - k.

This result is analogous to the classical Foata-Sch¨utzenberger equi-distribution theorem,

and implies that the quasi-symmetric generating function of descent set over 321-avoiding

permutations with a prescribed number of blocks is Schur-positive.

Joint work with Ron Adin and Yuval Roichman.

The goal of my talk (based on joint work with Vladimir Retakh) is to introduce and study noncommutative versions of Catalan numbers which belong to the free Laurent polynomial algebra L_n in n generators.

Our noncommutative Catalan numbers C_n admit interesting (commutative and noncommutative) specializations, one of them related to Garsia-Haiman (q,t)-versions, another -- to solving noncommutative

quadratic equations. We also establish total positivity of the corresponding (noncommutative) Hankel matrices H_n and introduce two kinds of noncommutative binomial coefficients which are instrumental

in computing the inverse of H_n and in other combinatorial identities involving C_n.

Let $G$ be a finite group, and let $\pi$ be a permutation from $S_n$. We study the distribution of probabilities of the equality

\[ a_1 a_2 \cdots a_n = a_{\pi_1}^{\epsilon_1} a_{\pi_2}^{\epsilon_2} \cdots a_{\pi_n}^{\epsilon_n}, \]

where $\pi$ varies over all the permutations in $S_n$, and $\epsilon_i$ varies either over the set $\{1, -1\}$ or over the set $\{1, b\}$, where $b$ is an involution in $G$ (two different cases of equations). The equation can also be written as

\[ a_1 a_2 \cdots a_n = a_{\pi_1} a_{\pi_2} \cdots a_{\pi_n}, \]

where $\pi$ is a signed permutation from $B_n$, and $a_{-i}$ is interpreted either as the inverse $a_i^{-1}$, in case $\epsilon_i \in \{1, -1\}$, or as the conjugate $b a_i b$, in case $\epsilon_i \in \{1, b\}$. The probability in the second case depends on the conjugacy class of the involution $b$.

First we consider the case in which all $\epsilon_i$ are $1$. It turns out that the probability, for a permutation $\pi$, depends only on the number of alternating cycles in the cycle graph of $\pi$, introduced by Bafna and Pevzner in 1998. We describe the spectrum of probabilities of permutation equalities in a finite group as $\pi$ varies over all permutations in $S_n$. We then generalize, letting a signed permutation vary over all the signed permutations in $B_n$, under the two interpretations outlined above. The spectrum turns out to be closely related to the partition of the number $2^{n}\cdot n!$ into a sum of the corresponding signed Hultman numbers (defined by Grusea and Labbare) when $\epsilon_i \in \{1, -1\}$, or into edge-signed Hultman numbers (introduced in this talk) when $\epsilon_i \in \{1, b\}$.

We introduce the notion of "one-sided epsilon-approximants", which is in strength between epsilon-nets and usual (two-sided) epsilon-approximants. Given an n-point set P in R^d, a one-sided epsilon-approximant for P (with respect to convex sets) is a multiset A such that, for every convex set C, we have |P cap C|/|P| - |A cap C|/|A| <= epsilon.

We show that, in contrast with the usual epsilon-approximants, every P has a one-sided epsilon-approximant with respect to convex sets of size g(eps, d) for some g, but independent of n.

Unfortunately, due to the use of a geometric Ramsey theorem, our bound is very weak: g(eps, d) <= 2^2^...^2^(1/epsilon)^c, with d-1 2's.

For more info, see arXiv:1603.05717

Joint work with Boris Bukh.

Hadwiger and Debrunner themselves showed that if q is very close to p, then C=p-q+1 suffices. The proof of Alon and Kleitman yields a huge bound C=O(p^{d^2+d}), and providing sharp upper bounds on the minimal possible C remains a wide open problem.

In this talk we show an improvement of the best known bound on C for all pairs (p,q). In particular, for a wide range of values of q, we reduce C all the way to the almost optimal bound p-q+1<=C<=p-q+2. This is the first near tight estimate of C since the 1957 Hadwiger-Debrunner theorem.

Joint work with Shakhar Smorodinsky and Gabor Tardos.

We show that for any rational polygon P in the plane, and any odd-sized collection of translates of P, the area of the set of points covered by an odd number of these translates is bounded away from 0 by a universal constant depending on P alone.

The key ingredient of the proof is a construction of an odd cover of the plane by translates of P. That is, we establish a family of translates of P covering (almost) every point in the plane a uniformly bounded odd number of times.

Joint work with Rom Pinchasi.

We introduce a new model for random knots and links, based on the petal projection developed by C. Adams et al. We study the distribution of various invariants of knots and links in this model. We view a knot invariant as a random variable on the set of all petal diagrams with n petals, and ask for its limiting distribution as n --> infinity. We obtain a formula for the limiting distribution of the linking number of a random two-component link. We obtain formulas for all moments of the two most basic Vassiliev invariants of knots, which are related to the Conway polynomial and the Jones polynomial. These are the first precise formulas given for the distributions or moments of invariants in any model for random knots and links.

Joint work with Chaim Even-Zohar, Joel Hass, and Nati Linial.

We discuss a generalization of k-suitable permutations, defined in 1950 by Dushnik in the context of the order dimension of the boolean lattice.

We relate suitable digraphs to communication settings and prove lower and upper bounds on the cardinality of families of (k,l)-suitable digraphs.

Joint work with Elad Haramaty, Aaron Potechin and Madhu Sudan.

The uncertainty principle in the n-dimensional hypercube states that if a non-zero function is supported in A and its Fourier transform is supported in B, then |A||B| is at least 2^n.

We consider a relaxed version, requiring only a non-negligible fraction of the l_2 norm of the function to be attained in A and of its transform in B. Provided either A or B is a Hamming ball, we give a description of the possible joint behavior of |A| and |B|. This description is tight on the exponential scale (that is, assuming both A and B are exponentially small). The main technical tool we use is a stronger version of the hypercontractive inequality for functions with exponentially small support.

As a corollary we show that any binary linear code contains "many" (in the appropriate sense) codewords whose length is close to that guaranteed by the linear programming bound.

Joint work with Yury Polyanskiy.

It is shown that for any fixed c \geq 3 and r, the maximum possible chromatic number of a graph on n vertices in which every subgraph of radius at most r is c-colorable is n^(1/r+1) up to a multiplicative factor logarithmic in n: in fact, it is O((n/log(n)) ^ (1/r+1)) and Omega(n^(1/r+1) / log(n)).

The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random n-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius r in it are 2-degenerate.

Joint work with Noga Alon.

For a graph on $n$ vertices, and an integer $D$, let the $D$-local view of $G=(V,E)$ be the collection (multiset) of the unlabelled $n$ balls of distance $D$ around the vertices.

The main question that motivates this study is: what can be said about $G$ knowing only its $D$-local view for some constant $D$.

For constant bounded degree planar (or more generally hyperfinite) graphs, Newman-Sohler [2011] following a long sequence of work, show that for any $\epsilon > 0$, there is a $D$ such that the $D$-local view of the graph determines the graph up to the deletion / insertion of at most $\epsilon n$ edges. This in turn, implies that every property of planar (hyperfinite) graphs can be tested (in the sense of property testing, by constantly many queries.

What happens in non-bounded degree planar graphs? The answer is currently still open. However, we show, following Yoshida's results on forests, that the above phenomenon still holds for outerplanar graphs. The implication to testing is deteriorated, though. Testing now requires $O(poly(\log n))$ queries.

I will describe the ideas behind the two results, the later which is a joint work with Jasine Babu and Areej Khoury.

Ramanujan graphs, constructed by Lubotzky, Phillips and Sarnak and known also as the LPS graphs, are certain quotients of the Bruhat-Tits building of PGL_2(Q_p). These graphs form a family of expander graphs, and serve as an explicit construction of graphs of high girth and large chromatic number. High dimensional counterparts of the LPS graphs are the Ramanujan Complexes, constructed by Lubotzky, Samuels and Vishne, as quotients of the Bruhat-Tits building of PGL_d over a non-archimedean field of finite characteristic. I'll talk about the mixing of these complexes, which implies that they have good expansion and large chromatic number.

If time permits, I'll talk about analogous results for general hypergraphs satisfying certain regularity condition.

Joint work with S.Evra, A.Lubotzky.

May the same graph admit two different chromatic numbers in two different universes? how about infinitely many different values? and can this be achieved without changing the cardinals structure?

The key concept of our discussion is that of a perfect matching (PM) in a bipartite graph. The expansion condition in Hall's marriage theorem can be extended to an unbiased 2-sided one. This enables an alternative (and simpler) proof of Evans' (proven) Conjecture:

A partial nxn Latin square with n-1 dictated entries admits a completion to a full Latin square.

PMs are used to successively fill the square by rows, columns or diagonals. Latin square tables correspond to quasi-groups; the ones corresponding to groups are only a tiny fraction of them, as n grows. However, for Sudoku tables of order mnxmn, the completion (say by diagonals) usually fails, even if there are no dictated entries, unless they are conjugates of a twisted product of two groups, of orders n and m.

An open problem for sudoku lovers: Is there a sudoku square (of any order) which is not a conjugate of a twisted product of groups?

No prior knowledge needed.

A normally regular digraph with parameters (v,k,λ,μ) is a directed graph with adjacency matrix A satisfying the equation AA^{T}=kI+λ(A+A^{T}) +μ(J-I-A-A^{T}). I.e., the number of common out-neighbours of vertices x and y is k if x=y, μ if x and y are non-adjacent, λ if x and y are adjacent in one direction and 2λ-μ if they are adjacent in both directions.

The adjacency matrix of a normally regular graph is normal, and all eigenvalues other than k are on one circle in the complex plane. This property characterizes normally regular digraphs.

We consider constructions and structural characterizations and we also consider connections to association schemes, symmetric 2-designs, generalized difference sets, and partition of a projective plane into subplanes.

The (still open) problem of determining the diameter of this graph is a trigger for an exciting tour through

reduced words of a Coxeter element in the symmetric group, a 0-Hecke algebra action, a special EL-labeling, q,t-Catalan numbers, and non-crossing alternating trees.

Joint work with Yuval Roichman.

Erdos-Ko-Rado (EKR) type theorems yield upper bounds on the size of set families under various intersection requirements on the elements. Stability versions of such theorems assert that if the size of a family is close to the maximum possible then the family itself must be close (in appropriate sense) to a maximum family.

Joint work with David Ellis and Nathan Keller.

The branching rules for representations of the symmetric group are one of the gems of representation theory. In this talk we will give a natural generalization of some branching rules to the case of a wreath product of a finite group with the symmetric group.

The rules we will generalize are the Littlewood-Richardson rule and the "classical" rules for inducting from S_{n} to S_{n+1} and restricting from S_{n+1} to S_{n}. If time allows we will give an application to the quiver computation of a natural family of categor algebras.

The goal of my talk (based on joint work with Dima Grigoriev, Anatol Kirillov, and Gleb Koshevoy) is to generalize the celebrated Robinson-Schensted-Knuth (RSK) bijection between the set of matrices with nonnegative integer entries, and the set of the planar partitions.

Namely, for any pair of injective valuations on an integral domain we construct a canonical bijection K, which we call the generalized RSK, between the images of the valuations, i.e., between certain ordered abelian monoids.

Given a semisimple or Kac-Moody group, for each reduced word ii=(i_1,...,i_m) for a Weyl group element we produce a pair of injective valuations on C[x_1,...,x_m] and argue that the corresponding bijection K=K_ii, which maps the lattice points of the positive octant onto the lattice points of a convex polyhedral cone in R^m, is the most natural generalization of the classical RSK and, moreover, K_ii can be viewed as a bijection between Lusztig and Kashiwara parametrizations of the dual canonical basis in the corresponding quantum Schubert cell.

Generalized RSKs are abundant in ``nature", for instance, any pair of polynomial maps phi,psi:C^m-->C^m with dense images determines a pair of injective valuations on C[x_1,...,x_n] and thus defines a generalized RSK bijection K_{phi,psi} between two sub-monoids of Z_+^m.

When phi and psi are birational isomorphisms, we expect that K_{phi,psi} has a geometric ``mirror image", i.e., that there is a rational function f on C^m whose poles complement the image of phi and psi so that the tropicalization of the composition psi^{-1}phi along f equals to K_{phi,psi}. We refer to such a geometric data as a (generalized) geometric RSK, and view f as a ``super-potential." This fully applies to each ii-RSK situation, and we find a super-potential f=f_ii which helps to compute K_ii.

While each K_ii has a ``crystal" flavor, its geometric (and mirror) counterpart f_ii emerges from the cluster twist of the relevant double Bruhat cell studied by Andrei Zelevinsky, David Kazhdan, and myself.

We provide tight lower and upper bound theorems for these polytopes as functions of $d,n$ and $s$, thus generalizing the classical Lower Bound Theorem by Barnette and Upper Bound Theorem by McMullen, which treat the case $s=0$. We characterize the minimizers and provide examples of maximizers, for any $d$.

Time permitting, I'll also discuss results on reconstruction problems for these and for related polytopes.

On page 155 of [Graham, Knuth and Patashnik] it says:

The numbers in Pascal's triangle satisfy, practically speaking, infinitely many identities,

so it is not surprising that we can find some surprising relationships by looking closely.

By proving some surprising identities in character tables of S_n we shall indicate that a

similar statement seem to hold for the S_n character tables .

Joint work with D. Zeilberger

In this talk we study short edge-disjoint paths in expander graphs(here it mean: graph with constant mixing time). We use the Lovasz Local Lemma to prove the following result: Given a d-regular expander graph G and a set L={(s_i,t_i)} such that each vertex of G appears at most O(d) times in the list, there exist a set of edge disjoint paths of constant length connecting each s_i to t_i. This result has applications to multiparty computation performed over networks in the presence of random noise.

Characterizing sets of permutations whose associated quasi-symmetric function is symmetric and Schur-positive is a long-standing problem in algebraic combinatorics. We will explain the significance of the problem and describe recent progress.

A general method to construct Schur-positive sets and multisets, based on pattern avoidance and geometric grids will be presented. This approach produces many new instances of Schur-positive sets, and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.

Joint with Sergi Elizalde.

The classical correlation inequality of Harris asserts that any two monotone increasing families on the discrete cube are nonnegatively correlated. In 1996, Talagrand established a lower bound on the correlation in terms of how much the two families depend simultaneously on the same coordinates. Talagrand's method and results inspired a number of important works in combinatorics and probability theory.

In this talk we present stronger correlation lower bounds that hold when the increasing families satisfy natural regularity or symmetry conditions. In addition, we present several new classes of examples for which Talagrand's bound is tight.

A central tool we use is a simple lemma asserting that for monotone events noise decreases correlation. This lemma gives also a very simple derivation of the classical FKG inequality for product measures, and leads to a simplification of part of Talagrand's proof.

Joint work with Gil Kalai and Elchanan Mossel

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.

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.

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.

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.

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 backgorund 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.

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.

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

Joint work with Noga Alon.

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.

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.

Ramsey's theorem states that for every symmetric partition of the square X^{2} of an infinite set X into finitely many cells, there would be a cell that covers the square Y^{2} of some infinite subset Y of X. Erdos and his collaborators considered various generalization of Ramsey's statement (replacing "infinite" with "uncountable", "finitely many" with "countably many", "square" with "rectangle"), and demonstraed the (consistent) failure of many of them. In this talk, we shall present this line of research, with the goal of elucidating the difference between rectangles and squares.

The theory of positional games is a branch of combinatorics,

whose main aim is to develop systematically an extensive

mathematical basis for a variety of two player perfect

information games, ranging from such commonly popular games as

Tic-Tac-Toe and Hex to purely abstract games played on graphs

and hypergraphs.

In this talk I will survey basic notions and concepts of

positional games and some recent developments in the field,

putting an emphasis on interconnections between positional games

and other branches of mathematics and computer science, in

particular probabilistic considerations.

Association schemes are one of the traditional areas of investigation in algebraic graph theory.

Catalogues of all association schemes are available from the website of Hanaki and Miyamoto. It is known that all association schemes of order up to 14 are Schurian, that is they are coming from suitable transitive permutation groups in the standard manner. First examples of non-Schurian association schemes exist on 15, 16 and 18 vertices. In particular, there are just two classes of non-Schurian association schemes of order 18.

Starting from successful computer free interpretations of these two examples, and using extensive computer algebra experiments in conjunction with further reasoning, we were able to observe the existence of at least four infinite families of non-Schurian association schemes of order 2p^2 (for p prime, p>3).

This is joint work with M. Klin.

In this talk we consider Maker-Breaker games played on random boards. Given a graph G=(V,E) and a graph property P, the Maker-Breaker game P played on G is defined as follows. In every round Maker and Breaker alternately claim free edges from E. Maker wins this game as soon as his graph possesses P. Otherwise, Breaker wins the game.

We consider the perfect matching, hamiltonicity and k-connectivity games played on a sparse random board G(n,p), p>=polylog(n)/n. It is clear that Maker needs at least n/2, n, kn/2 moves to win these games, respectively. We prove that G(n,p) is typically such that Maker has a strategy to win

within n/2+o(n), n+o(n), kn/2+o(n) moves, respectively. We also show a connection between fast strategies in Maker-Breaker games (weak games) and Maker-Maker games (strong games).

Joint work with Dennis Clemens, Anita Liebenau and Michael Krivelevich.

**Note: The talk will be given in Hebrew.**

For a set P of points in the plane, the Simple Spanning Tree (SST) graph on P, denoted by G(P), is a graph whose "vertices" are simple (i.e., non-crossing) trees whose set of vertices is P, such that two trees are connected by an "edge" if their symmetric difference contains only two edges.

In this talk we would like to characterize the center of G(P). It turns out that the center of G(P) is related to the notion of a blocker for SSTs, defined as a set of edges which has at least one edge in common with any SST on P.

First, we give a complete characterization of the blockers which are smallest w.r.t. the number of edges. Concretely, we show that these are either stars (i.e., trees of diameter 2) or special structures called "caterpillars", that were first studied by Harary and Schwenk in 1971, and appear in diverse applications in graph theory.

Then we use the minimal blockers to give an almost complete characterization of the center of G(P). We show that all the elements of the center are minimal blockers, and that all the "caterpillar" minimal blockers are elements of the center. Thus, the only remaining case is the stars, for which we show that some are elements of the center, while others are not.

Based on joint works with Micha Perles, Eduardo Rivera-Campo, and Virginia Urrutia-Galicia.

A knot is a circle embedded in three-space, but we immediately translate it into a bipartite graph Gamma following previous work of the author. We consider the graph G of perfect matchings of this graph Gamma, providing a combinatorial formula for the width of G. We present several properties of Gamma and construct a partition of its vertices into cycles that relate directly to G.

This work was inspired by a seminar talk by Roy Ben-Ari on part of his Masters thesis under the supervision of Ron Adin and Yuval Roichman.

This is joint work with Mina Teicher.

Coherent configurations (CC's), in the sense of D.G. Higman, play a central role in algebraic graph theory. They capture some of the combinatorial properties of permutation groups. However in contrast to other combinatorial structures, no catalogue of such configurations of small order exists. Our long term goal is to fill this gap.

We can classify coherent configurations according to the number of fibers (a combinatorial analogue of orbits of permutation groups). CC's with one fiber are actually association schemes, and for this type of structure a catalogue exists, see http://kissme.shinshu-u.ac.jp/as/.

It is natural to consider CC's with two fibers next.

One particular case of two-fiber CC's is equivalent to strongly regular designs (SRD's), a class of block designs introduced by Higman in 1988. While Higman originally was interested only in structures with primitive point and block graphs, we consider also the imprimitive case. We will

describe our approach to construct all small SRD's and will consider a list of feasible parameter sets that we generated. Then we will give two examples: A classical object (Reye's configuration, discovered in 1882) in a new disguise, and a new object, namely the smallest non-Schurian

SRD with 8 points and 12 blocks.

This is a joint project with Mikhail Klin.

Hindman's Theorem asserts that, for each finite coloring of $\N$, there are distinct $a_1, a_2, \dots \in \N$ such that all sums $a_{i_1} + a_{i_2} + \dots + a_{i_m}$ ($m \ge 1$, $i_1 < i_2 < \dots < i_m$) have the same color. Shevrin's classification of semigroups and a proof of Hindman's Theorem, due to Galvin and Glazer, imply together that, for each infinite semigroup $S$, there are distinct $a_1, a_2, \dots \in S$ such that all but finitely many of the products $a_{i_1}a_{i_2}\cdots a_{i_m}$ ($m \ge 1$, $i_1 < i_2 < \dots < i_m$) have the same color.

Using these methods, we characterize the semigroups $S$ such that, for each finite coloring of $S$, there is an infinite subsemigroup $T$ of $S$, such that all but finitely many members of $T$ have the same color.

Simple proofs. No background is needed.

Joint work with Boaz Tsaban.

The flag f-vector is a basic invariant of finite graded posets, counting chains according to the set of ranks they occupy. For Eulerian posets it is efficiently encoded by the cd-index, a noncommutative polynomial in variables $c$ and $d$ with integer coefficients. Moreover, if the poset is Gorenstien*, in particular if the order complex of its proper part is topologically a sphere, then Karu proved Stanley's conjecture that all the coefficients of the cd-index are nonnegative. What more can be said about the cd-index of Gorenstein* posets? Upper bounds? A characterization?

We characterize the cd-index for rank 5 (lower ranks are easy, rank 5 corresponds to 3-dimensional spheres), obtain upper bounds for certain coefficients in all ranks, and conjecture further upper bounds for the entire cd-index.

Reflects joint with Satoshi Murai.

All needed background will be given in the talk!

A 1-factorization of the complete graph Kn is a partition of its edges into n-1 perfect matchings. A Steiner triple system on [n] = {1,...,n} is a collection T of triples such that each pair in [n] is contained in a unique triple.

We will discuss the connections between these (and other) objects, and present previously known bounds on their number. We'll prove that the number of 1-factorizations of Kn is at most ((1+o(1)) n/e^2)^(n^2/2) and that the number of Steiner triple systems on [n] is at most ((1+o(1)) n/e^2)^(n^2/6).

The proofs make use of information entropy.

Joint work with Nati Linial.

- תאריך עדכון אחרון: 17/10/2017