Abstracts

Flips, group actions and tableaux
Yuval Roichman, Bar-Ilan University

Abstract: Flips of diagonals in a triangulation of a convex polygon have various interpretations, which lead to a solution of a conjecture of Richard Stanley. Several recent mysterious enumerative results on shifted Young tableaux and on pattern avoidance follow. A representation theoretic explanation of these results is desired.

Joint with Ron Adin, Ronald King and Sergi Elizalde.

Back

The speed process of TASEP (Totally ASymmetric Exclusion Process)
Gidi Amir, Bar-Ilan University

Abstract: We study an exclusion process on Z where each particle is assigned a class (number in Z) and each particle tries to swap places with its right neighbor with rate 1 if that neighbor has a higher class number. (Alternatively, each edge of Z is "sorted" with rate 1.) With the right starting conditions, the position of each particle (normalized by time) converges to a constant speed. The speed of each particle is uniform in [-1,1], but there are strong dependencies between the behaviors of different particles. We study the joint distribution of these speeds – the TASEP speed process.

We prove that the TASEP speed process is stationary with respect to the multi-type TASEP dynamics, where speeds are considered as the classes of the particles. Consequently, every ergodic stationary measure is given as a projection of the speed process measure. This allows us to utilize known results on the stationary measure for the multi-type TASEP to deduce various marginals of the speed process, such as the joint distribution of the speeds for 3 successive particles. Another surprising consequence is the existence of infinite "convoys" – particles (with different classes) all converging to the same speed.  Some of our results apply also to the partially asymmetric case.

No prior knowledge on exclusion processes is assumed, and all definitions will be given within the lecture.

This is joint work with Omer Angel and Benedek Valko.

Back

Permutation statistics in the affine Coxeter group of type A
Eli Bagno, Jerusalem College of Technology

Abstract: The theory of permutation statistics on infinite groups is still not well developed. One of the main problems is that many of the classical combinatorial parameters used in the finite case have a finite range. A choice of such a parameter on an infinite group would yield no reasonable generating function. Hence many of the nice and elegant identities known, for example, for the classical Weyl groups, do not exist for the affine case.

In this work we present a combinatorial parameter with an infinite range on the affine Coxeter group of type A, which equidistributes with the length function over this group. The nice behavior is only over the 'positive part' of the group, but here the idea of Hilbert's Hotel comes to our aid. Our parameter also has an algebraic meaning. In previous works it has been shown that the coinvariant algebra of the symmetric group, which is isomorphic to its regular representation, can be decomposed into sub representations corresponding to combinatorial parameters such as the descent functions and the major index. These results were extended to all classical finite Coxeter groups and also to the colored permutation groups.

This idea is implemented in the case of the affine Coxeter group of type A, using our new parameter.

Back

Random walks on the symmetric group
Gady Kozma, Weizmann Institute of Science

Abstract: The group of all permutations of n elements is perhaps the most studied finite non-abelian group, in terms of random walks on it. An exciting aspect of the field is that every question can be approached probabilistically or algebraically, and people reached impressive results both using and not using its theory of representations. We will survey old and new results, and connections to the quantum Heisenberg ferromagnet. No prior knowledge of representation theory (or physics) will be assumed.

Back

Topology of random complexes
Roy Meshulam, Technion

Abstract: Let Y be a random d-dimensional subcomplex of the (n-1)-simplex S, obtained by starting with the full (d-1)-dimensional skeleton of S and then adding each d-simplex independently with probability p. When d=1, the topology of the random graph Y=G(n,p) is thoroughly understood.
We'll describe some recent work on the topology of Y for d>1, where much less is known. In particular, we'll discuss results concerning:
1. The threshold probability for vanishing of the (d-1)-dimensional homology of Y (joint work with N. Linial and with N. Wallach).
2. The threshold probability for the vanishing of the d-dimensional homology of Y (joint work with L. Aronshtam, N. Linial and T. Luczak).

Back

A simple geometric lemma and an application
Rom Pinchasi, Technion

Abstract: We show the following geometric fact. Let $C$ be a compact convex set in the plane and let $\alpha>0$ be given. There exists a point $O \not in C$ such that $O$ sees $C$ at angle $\alpha$ and the two tangents from to $C$ from $O$ meet $C$ at two single points $A$ and $B$ such that $|OA|$=$|OB|$.

We show an interesting application of this lemma to combinatorial geometry. This is joint work with Eyal Ackerman and Tsachik Gelander.

Back

A dimer model for the Jones polynomial of pretzel knots
Moshe Cohen, Bar-Ilan University

Abstract: This work gives the construction of an "activity matrix" whose determinant gives Tutte's activity words associated with spanning trees of the signed Tait graph coming from a pretzel knot diagram. Evaluations of these activity words give the signed Tutte polynomial, the Kauffman bracket polynomial, and the Jones polynomial, as well as some applications to the reduced Khovanov homology chain complex. This construction holds for some more general knot diagrams, as well. Furthermore, this discussion conforms to the language of dimers or perfect matchings on a bipartite graph.

Back

The unlikeliness of being covered
Ori Gurel-Gurevich, Univeristy of British Columbia, Vancouver

Abstract: We will show that the probability that a simple random walk will cover a finite, bounded degree graph in linear time is exponentially small. More precisely, for every D and C, there exists a=a(D,C)>0 such that for any graph G, with n vertices and maximal degree D, the probability that a simple random walk, started anywhere in G, will visit every vertex of G in its first Cn steps is at most $exp(-an)$.

Joint work with Itai Benjamini and Ben Morris.

Back

Expanders, Ramanujan graphs and random lifts
Benny Sudakov, UCLA

Abstract: Expansion of a graph is one of the most fundamental concepts in modern combinatorics, which has numerous applications in many mathematical areas. It is well known that expansion is closely relates to the spectral properties of the graph. The celebrated Alon-Boppana bound says that all eigenvalues of a d-regular graph must be at least 2sqrt(d-1) - o(1), and graphs that meet this bound are called Ramanujan Graphs. There are still many unresolved questions about the existence of such graphs. In this talk we survey this background material, and then explain what lifts of graphs are and how the above questions can be approached using random lifts of graphs.

Joint work with Lubetzky and Vu.

Back

On the growth functions of semigroups
Lev Shneerson, CUNY

Abstract: We study the asymptotic behavior of the growth functions in some classes of finitely generated and finitely presented semigroups and investigate conditions under which these semigroups have polynomial growth. In particular, we find new criteria for polynomial growth in finitely presented Rees quotients of free inverse semigroups.

Most of the results of the talk are joint work with David Easdown (School of Mathematics and Statistics, The University of Sydney, Australia)

Back

Discrete harmonic analysis of Boolean functions and its applications
Nathan Keller, Weizmann Institute of Science

Abstract: Boolean functions are a central object of study in combinatorics, complexity theory, probability theory and other areas of mathematics and computer science. In a paper from 1988, Kahn, Kalai and Linial (KKL) introduced the use of tools from harmonic analysis in the study of Boolean functions. The paper of KKL was the starting point of an entire area of research. In the last two decades the results of KKL were greatly expanded, the analytic tools were developed significantly, and the techniques were applied in numerous fields, including percolation theory, learning theory, social choice theory, etc.

In this talk we will present the basic objects of study (e.g., influences, Fourier-Walsh expansion etc.) and the basic analytic tools (e.g. hypercontractive inequalities), and then we will show several new applications, focusing on applications to correlation inequalities, percolation theory, and social choice theory.

Some of the results are based on joint works with Guy Kindler, and with Ehud Friedgut, Gil Kalai, and Noam Nisan.

Back

I am almost a perfect matchmaker
David Howard, Technion

Abstract: Matching theory in graphs is a well studied and understood field of mathematics. There are nice theorems that give sufficient and necessary conditions for guaranteeing the existence of large matchings. In contrast, matching theory in hypergraphs is far less understood, and finding such conditions for hypergraph matchings is still unknown in many cases.

In this talk I will give certain degree conditions in r-partite hypergraphs that guarantee the existence of large (almost perfect) matchings. Additionally, I will present a variety of related open problems and conjectures in the field.

Back