# Combinatorics

מארגן/מארגנים:
מארגן/מארגנים:
Usual Time:
Place:

### Previous Lectures

Robert Shwartz (Ariel University)
19/06/2016 - 14:00 - 15:30

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\}$.

Gabriel Nivasch (Ariel University)
29/05/2016 - 14:00 - 15:30

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.

Joint work with Boris Bukh.

Chaya Keller (Ben-Gurion University)
22/05/2016 - 14:00 - 15:30

The classical Helly's theorem states that if in a family of compact convex sets in R^d  every d+1 members have a non-empty intersection then the whole family has a non-empty intersection. In an attempt to generalize Helly's theorem, in 1957 Hadwiger and Debrunner posed a conjecture that was proved more than 30 years later in a celebrated result of Alon and Kleitman:
For any p,q  (p >= q > d) there exists a constant C=C(p,q,d) such that the following holds:
If in a family of compact convex sets, out of every p members some q intersect, then the whole family can be pierced with C points.

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.

Yuri Rabinovich (University of Haifa)
15/05/2016 - 14:00 - 15:30

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.

Tahl Nowik (Bar-Ilan University)
08/05/2016 - 14:00 - 15:30
Random knots

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.

Rani Hod (Bar-Ilan University)
01/05/2016 - 14:00 - 15:30

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.

Alex Samorodnitsky (Hebrew University, Jerusalem)
10/04/2016 - 14:00 - 15:30

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.

Omri Ben Eliezer ׂ(Tel-Aviv University)
03/04/2016 - 14:00 - 15:30

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.

Ilan Newman (University of Haifa)
27/03/2016 - 14:00 - 15:30

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.

Konstantin Golubev (Hebrew University, Jerusalem)
20/03/2016 - 14:00 - 15:30

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.

Assaf Rinot (Bar-Ilan University)
13/03/2016 - 14:00 - 15:30

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?

In this talk, we shall give various examples of graphs+universes that address the above questions.

Eli Shamir (Hebrew University, Jerusalem)
06/03/2016 - 12:00 - 13:00

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.

Leif Jørgensen (Aalborg U, Denmark)
17/01/2016 - 14:00 - 15:30

A normally regular digraph with parameters (v,k,λ,μ) is a directed graph with adjacency matrix A satisfying the equation AAT=kI+λ(A+AT) +μ(J-I-A-AT).  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.

10/01/2016 - 14:00 - 15:30
The maximal chains in the non-crossing partition lattice have a natural graph structure.
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.

We shall describe connections, results and open problems in this context.

Joint work with Yuval Roichman.

Noam Lifshitz (BIU)
03/01/2016 - 14:00 - 15:30

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.

In this talk we present an approach to stability versions of EKR-type
theorems through isoperimetric inequalities for subsets of the hypercube.
We use this approach to obtain tight stability versions of the EKR theorem itself and of
the Ahlswede-Khachatrian theorem on t-intersecting families (for k < n/(t+1)),
and to show that, somewhat surprisingly, both theorems hold when the "intersection"
requirement is replaced by a much weaker requirement.

Furthermore, we obtain stability versions of several recent EKR-type results, including
Frankl's proof of the Erdos matching conjecture for n>(2s+1)k-s.

Joint work with David Ellis and Nathan Keller.

Itamr Stein (BIU)
27/12/2015 - 14:00 - 15:30

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.

20/12/2015 - 14:00 - 15:30
Generalized RSK

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.

Eran Nevo (Hebrew U)
29/11/2015 - 14:00 - 15:30
We study $n$-vertex $d$-dimensional polytopes with at most one nonsimplex facet with, say, $d+s$ vertices, called almost simplicial polytopes.

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.

This is joint work with Guillermo Pineda-Villavicencio, Julien Ugon, David Yost.

Amitai Regev (Weizmann)
22/11/2015 - 14:00 - 15:30

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

Stuart Margolis (BIU)
15/11/2015 - 14:00 - 15:30
Boolean representable simplicial complexes are a generalization of matroids based on
independence over the Boolean semiring. The work was pioneered by work of Izhakian and
Rowen at Bar-Ilan on notions of rank and independence over semirings. It was later defined
and initially developed by Izhakian and Rhodes and later Silva.

In this talk it is proved that fundamental groups of boolean representable simplicial complexes
are free and the rank is determined by the number and nature of the connected
components of their graph of flats for dimension ≥ 2. In the case of dimension 2, it
is shown that boolean representable simplicial complexes have the homotopy type of
a wedge of spheres of dimensions 1 and 2. Also in the case of dimension 2, necessary
and sufficient conditions for shellability and being sequentially Cohen-Macaulay are
determined. These notions are equivalent in dimension 2, but despite having the appropriate homotopy type,
not all 2 dimensional boolean representable simplicial complexes are shellable.
Complexity bounds are provided for all the algorithms involved.

All terms will be defined. This is joint work of the speaker, John Rhodes and Pedro Silva.
Klim Efremenko (Tel-Aviv U)
08/11/2015 - 14:00 - 15:30

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.

Yuval Roichman (BIU)
01/11/2015 - 14:00 - 15:30

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.

Nathan Keller (BIU)
25/10/2015 - 14:00 - 15:30

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

Shay Moran (Technion)
11/01/2015 - 14:00 - 15:30

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.

Chaya Keller (Hebrew University)
04/01/2015 - 14:00 - 15:30
Let $P$ be a finite set of points in general position in the plane. The structure of the complete graph $K(P)$ as a geometric graph includes, for any pair $[a,b],[c,d]$ of vertex-disjoint edges, the information whether they cross or not.

The simple (i.e., non-crossing) spanning trees (SSTs) of $K(P)$ are the vertices of the so-called Geometric Tree Graph of $P$, $G(P)$. Two such vertices are adjacent in $G(P)$ if they differ in exactly two edges, i.e., if one can be obtained from the other by deleting an edge and adding another edge. Introduced by Avis and Fukuda in 1993, geometric tree graphs were studied in a number of papers and play an important role in algorithms for spanning trees enumeration.

In this talk we show how to reconstruct from $G(P)$ (regarded as an abstract graph) the structure of $K(P)$ as a geometric graph. This result can be viewed as a geometric counterpart of a work of Sedlacek (1974) on reconstruction of an abstract graph from the list of its spanning trees, and may shed light on the structure of the automorphism group of $G(P)$ whose determination is a 15-years old open problem.

Joint work with Micha A. Perles.

Note: The talk will be given in Hebrew.

Miriam Farber (MIT)
28/12/2014 - 14:00 - 15:30

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.

Tali Kaufman (Bar-Ilan University)
14/12/2014 - 14:00 - 15:30

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.

Karim Adiprasito (IHES and Hebrew University)
07/12/2014 - 14:00 - 15:30

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.

Yuval Peled (Hebrew University)
30/11/2014 - 14:00 - 15:30

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.

Clara Shikhelman (Tel-Aviv University)
23/11/2014 - 14:00 - 15:30

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

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

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

Joint work with Noga Alon.

Avraham Morgenstern (Hebrew University)
16/11/2014 - 14:00

The Erd\H{o}s-Hajnal conjecture states that for every graph H there exists an injection of H into G for every large graph G whose largest homogeneous subset (clique or anti-clique) is sub-polynomial in |G|. We formulate a local version of this conjecture, and prove it for all 3-vertex graphs H. We prove the tournament analog for all 4-vertex tournaments H.

We initiate the study of the 4-local profiles of tournaments, and derive some bounds on these sets. In particular, given the number of cycles of length 3, which tournaments minimize the number of cycles of length 4? Given the number of transitive triangles, which tournaments minimize the number of transitive quadruples? We state a conjecture, and derive an almost matching bound. We show that these two questions are equivalent, and describe some related questions. For example: Can the cyclic triangles be uniformly distributed along the edges of a large tournament?  (answer: No, except for trivial cases).

Joint Work with Nati Linial.
Noam Lifshitz (Bar-Ilan University)
09/11/2014 - 14:00

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.

Shira Zerbib (Technion)
02/11/2014 - 14:00

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.

Assaf Rinot
24/11/2013 - 14:00

Ramsey's theorem states that for every symmetric partition of the square X2 of an infinite set X into finitely many cells, there would be a cell that covers the square Y2 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.

Biblography

Michael Krivelevich, Tel Aviv University
13/05/2012 - 12:00

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.

Stefan Gyurki, Ben-Gurion University, Beer Sheva, and Slovak University of Technology, Bratislava
06/05/2012 - 14:00

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.

Asaf Ferber, Tel-Aviv University
29/04/2012 - 14:00

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.

Chaya Keller, Hebrew University
22/04/2012 - 14:00

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.

Moshe Cohen, Bar-Ilan University
15/04/2012 - 14:00

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.

Sven Reichard, Essen and Ben-Gurion University
25/03/2012 - 14:00

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.

Gili Golan, Bar-Ilan University
18/03/2012 - 14:00

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.

Eran Nevo, Ben-Gurion University
11/03/2012 - 14:00

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!

Zur Luria - Hebrew University
04/03/2012 - 14:00

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.