Abstracts

On the correlation of monotone families
Nathan Keller, Bar-Ilan University

Abstract: 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.

Back

Schur positivity via pattern avoidance
Yuval Roichman, Bar-Ilan University

Abstract: 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.

Back

Short paths in expander graphs
Klim Efremenko, Tel-Aviv University

Abstract: In this talk we study short edge-disjoint paths in expander graphs (here it means: graphs 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 exists 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.

Back

On shellability, Cohen-Macauleyness and the homotopy type of Boolean representable simplicial complexes
Stuart Margolis, Bar-Ilan University

Abstract: 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.

Back

Some surprising identities in character tables of S_n
Amitai Regev, Weizmann Institute of Science

Abstract: 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.

Back

Almost simplicial polytopes
Eran Nevo, Hebrew University

Abstract: 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.

Back

Generalized RSK
Arkady Berenstein, University of Oregon

Abstract: 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.

Back

Branching rules for wreath products
Itamar Stein, Bar-Ilan University

Abstract: 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 category algebras.

Back

Stability versions of Erdos-Ko-Rado type theorems via isoperimetry
Noam Lifshitz, Bar-Ilan University

Abstract: 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.

Back

Non-crossing partitions and a diameter problem
Ron Adin, Bar-Ilan University

Abstract: 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.

Back

Normally regular digraphs
Leif Jørgensen, Aalborg University, Denmark

Abstract: 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.

Back