# Combinatorics

### Upcoming Lectures

Let G be a finite group. Every word w in the free group on, say, 2 generators x and y, induces a probability measure on G as follows: sample two uniformly random elements g and h from G and evaluate w(g,h) to get an element of G. For example, if w = xyxy^{-2}, one obtains the random element ghgh^{-2} in G. The study of word measures on groups has revealed a lot of beautiful structure with surprising connections to other fields of mathematics, and has shed light on the finite group G as well as on the free group.

In this talk I will survey some of what we know and some of the challenges ahead, and focus on one illustrating example.

This is based on joint works with Liam Hanany, Michael Magee, Chen Meiri, Ori Parzanchevski and Danielle West.

### Previous Lectures

Let X be a simplicial complex. Given a simplex σ ∈ X of dimension at most d − 1 that is contained in a unique maximal face of X, the operation of removing σ and all the simplices that contain it from X is called an elementary d-collapse. We say that X is d-collapsible if it can be reduced to the void complex by performing a sequence of elementary d-collapses. The collapsibility of X is the minimal d such that X is d-collapsible. The notion of d-collapsibility was introduced by Wegner, who applied it in the study of intersection patterns of convex sets in R^d .

We study the collapsibility of simplicial complexes associated to different properties of graphs and hypergraphs, and present several topological and combinatorial applications. We discuss some of the tools that we use for bounding the collapsibility of a complex. In particular, we present a useful and easy to apply bound, generalizing a method due to Matoušek and Tancer.

The talk is partly based on joint work with Minki Kim.

We are given a 2-coloring of the edges of the complete graph. If the number of red edges in triangles is almost always even, then the coloring is approximately defined on vertices. Thus triangles "test" a function on edges to be defined from the vertices.

Replacing triangles by squares, and going up in the dimension, we show that differentials can test properties, as long as the cohomology group is sufficiently well understood.

Joint work with David Garber.

In 1974 Rick Wilson proved one of the most important theorems on combinatorial structures in the 20th century by showing that the easy necessary conditions on the parameters of a block design are eventually sufficient. The proof involves morphisms between block designs whose fibers allow for recursive constructions. The self-maps of a design form a monoid that are a fundamental part of the theory of designs. The algebraic properties of this monoid have not been explored up to now and the purpose of this talk is to do just that. We give a beautiful connection between semigroups, groups designs and incidence geometry.

No background in either design theory or semigroup theory is required for the talk. This is joint work with John Rhodes and Pedro Silva.

The goal of my second talk on the subject (the first one was given at this seminar two years ago), which is also based on joint work with Vladimir Retakh, is twofold:

First, I will recall motivations, definition and basic properties of noncommutative Catalan numbers C_n, which belong to the free Laurent polynomial algebra in x_0,...,x_n. They admit interesting (commutative and noncommutative) specializations, one of them related to the Garsia-Haiman (q,t)-version Catalan numbers, another -- to solving noncommutative quadratic equations. We also established total positivity of the corresponding (noncommutative) Hankel matrices H_n and introduced two kinds of noncommutative binomial coefficients which are instrumental in computing the inverse of H_n, its positive factorizations, and other combinatorial identities involving C_n.

Second, I will outline a relationship of the C_n with (noncommutative) orthogonal polynomials, which can be viewed as "characteristic polynomials" of an extended version of the matrices H_n or of the corresponding noncommutative Jacobi matrices J_n.

We say that a family F of k-element sets is a j-junta if there is a set J of size j such that, for any set, its presence in F depends on its intersection with J only. Approximating arbitrary families by j-juntas with small j is a recent powerful technique in extremal set theory.

The weak point of all known approximation by juntas results is that they work in the range n>Ck, where C is an extremely fast growing function of the input parameters. In this talk, we present a simple and essentially best possible junta approximation result for an important class of families, called shifted. As an application, we present some progress in the question of Aharoni and Howard on families with no cross-matching.

Joint work with Peter Frankl.

Several items have to be allocated among several families. In each family, there are members with different preferences over the items. The goal is to divide the items such that, in each family, as many members as possible will perceive the division as "fair".

I will show that this problem combines two seemingly-unrelated problems: fair allocation of items among individuals, and finding winning-strategies in combinatorial games. I will present division algorithms, upper bounds and some open questions.

Joint work with Warut Suksompong (Oxford University).

**Full paper**: https://arxiv.org/abs/1709.02564

Erdos and Purdy conjectured that for n \geq 5 one cannot find a set of n red points in general position and another set of n-1 blue points such that every line determined by two red points passes also through a blue point. This conjecture is trivially true for n odd, but turns to be very challenging for n even. The conjecture is, in fact, a special (but important) case of the Magic Configuration conjecture of Murty from 1971. The conjecture of Murty was proved in 2008 in a topological setting.

Here we present a purely algebraic proof of the conjecture of Erdos and Purdy. On the way we also provide a nice result on vectors in the two dimensional plane.

A map $Y: X \rightarrow \{+1, -1\}$ over a finite set $X \con R^d $ is (linearly) separable if there exists $w \in R^d$ such that $\sign(w \bigcdot x)=Y(x)$ for all $x \in X$. When the Euclidean norm of $w$ is $\|w\|=1$, the number $\marg (w,Y) = \min_{x \in X} {Y(x) w\bigcdot x }$ is the margin of $w$ with respect to $Y$. The number $\marg(Y) = \sup_{w \in R^d : \|w\|=1} \marg(w,Y)$ is the margin of $Y$. We call $Y$ an $\eps$-partition if its margin is at least $\eps$.

Given a set $X$ of size $n$, how many $\eps$ partitions exist?

To answer this question, we will use the classical perceptron algorithm (the first neural algorithm). We will also use the perceptron to prove a "sparse" version of Farkas' lemma and derive generalization bounds using sample compression schemes. If time permits, we will also discuss some open combinatorial problems in learning theory.

The degree anti-Ramsey number of a graph H is the smallest integer k for which there exists a graph G with maximum degree at most k such that any proper edge colouring of G yields a rainbow copy of H (i.e., all edges of this copy of H have distinct colours).

We determine the degree anti-Ramsey number of any tree, and then extend this to any forest using a classical result of Bollobas concerning cross intersecting families. We also use a topological version of Hall's Theorem due to Aharoni, Berger and Meshulam to get an upper bound (which is best possible up to a factor of 2) on the degree anti-Ramsey numbers of cycles of any length, .

Joint work with Danny Hefetz.

Let V be an n-dimensional space over a fixed finite field. The complex of flags X(V) is the simplicial complex whose vertices are the non-trivial linear subspaces of V, and whose simplices are ascending chains of subspaces. This complex, also known as the spherical building associated to the linear group GL(V), appears in a number of different mathematical areas, including topology, combinatorics and representation theory. After recalling the classical homological properties of X(V), we will discuss some more recent results including:

1. Minimal weight cocycles in the Lusztig-Dupont homology.

2. Coding theoretic aspects of X(V) and the existence of homological codes.

2. Coboundary expansion of X(V) and its applications.

The random Linial-Meshulam complex Y_d(n,p) is the higher-dimensional analogue of the random graph model G(n,p). In recent years, the properties of random hypergraphs and simplicial complexes have been studied intensively. In this talk, we consider the fundamental group of a random 2-dimensional simplicial complex.

Babson, Hoffman and Kahle proved that the threshold for the fundamental group to vanish, i.e. simple connectivity, is approximately p=n^(-1/2). We show that in fact this threshold is at most (c n)^(-1/2) for c=4^4/3^3, and conjecture that this is the true threshold. In fact, we prove a sharp threshold for the stronger property that every cycle is the boundary of a subcomplex of Y_2(n,p) that is homeomorphic to a sphere.

The talk is based on a joint work with Yuval Peled.

An order-$n$ Latin square is equivalent to a triangle-decomposition of the complete tripartite hypergraph $K_{n,n,n}$. Let $H \sim H_3(n,n,n;p)$ be a tripartite, balanced, binomial random $3$-uniform hypergraph on $3n$ vertices where each edge is present with probability $p$. What is the threshold $p$ for the property that $H$ contains a Latin square? The general heuristic is that spanning structures appear together with the disappearance of local obstructions. Thus the natural conjecture is $p = 2 \log(n) / n$, which corresponds to the disappearance of edges not contained in any triangle.

While this problem remains open, two natural approaches are to consider approximations of Latin squares, and to obtain (possibly suboptimal) upper bounds on the threshold probability. I will review results in both directions.

The lion's share of the talk will be spent discussing an application of Keevash's method of randomized algebraic construction to show an upper bound of $n^{-1/7+ o(1)}$ on the threshold probability.

Parts of the talk are the result of joint work with Zur Luria.

Helly's theorem is a classical result in combinatorial geometry about the intersection patterns of convex sets in Euclidean spaces. For the 2-dimensional case, it asserts that for a family of convex sets in the plane, if every 3 members have a point in common, then all members in the family have a point in common. The topological Helly theorem, also proved by Helly, shows that the same assertion holds for a family of open and contractible sets where each intersection is again open and contractible.

In this talk, I will present Helly-type theorems for a more general set-system: a family of open connected sets in the plane where any intersection is again open and connected. In this setting, if every 4 members have a point in common, then all members in the family have a point in common. I will also discuss a fractional generalization of this.

Aldous' spectral gap conjecture, proved in 2009 by Caputo, Liggett and Richthammer, states the following a priori very surprising fact: the spectral gap of a random walk on a finite graph is equal to the spectral gap of the interchange process on the same graph.

This seminal result has a very natural interpretation in Representation Theory, which leads to natural conjectural generalizations. In joint works with Gadi Kozma and Ori Parzanchevski we study some of these possible generalizations, clarify the picture in the case of normal generating sets and reach a more refined, albeit bold, conjecture.

Experimentally, the convex-layer decomposition of subsets of the integer grid ("grid peeling") seems to behave at the limit like the affine curve-shortening flow. We offer some theoretical arguments to explain this phenomenon. In particular, we derive some rigorous results for the special case of peeling the quarter-infinite grid: We prove that, in this case, the number of grid points removed up to iteration n is Theta(n^(3/2)log n), and moreover, the boundary at iteration n is sandwiched between two hyperbolas that are separated from each other by a constant factor.

Joint work with David Eppstein and Sariel Har-Peled.

**The representation theory of monoids associated to Coxeter groups and other combinatorial structures**

In the last twenty years it has been noticed that many combinatorial and geometric structures also have the structure of a monoid. These include real and complex hyperplane arrangements, Bruhat order of Coxeter groups, Schubert cells of linear algebraic groups and more.

The representation theory of these monoids can be used to study random walks and give other information about these structures. Connections between combinatorial and geometric structures and representations of finite monoids has led to important developments in these fields.

In this talk, we look at the monoids associated to the Coxeter complex and to the Bruhat order of a Coxeter group. No previous knowledge required.

I'll describe a search game with a surprising geometric connection. A hunter and a rabbit move on an n-vertex graph without seeing each other until they meet. At each step, the hunter moves to a neighboring vertex or stays in place, while the rabbit is free to jump to any node. Thus they are engaged in a zero sum game, where the payoff is the capture time. We show that an optimal rabbit strategy for the cycle yields a Kakeya set: a plane set of zero area that contains a unit segment in every direction. Kakeya sets have been studied intensively in harmonic analysis since their discovery by Besicovitch (1919); their connection to search games is new and yields insights in both directions. (Based on joint work with Y. Babichenko, R. Peretz, P. Sousi and P. Winkler and on earlier work by Adler et al (2003).)

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.

- תאריך עדכון אחרון: 14/10/2018