Abstracts

Representation theory of the infinite symmetric group and point processes of random matrix type
Evgeny Strahov, Hebrew University

Abstract: The aim of my talk is to describe determinantal and Pfaffian point processes of random matrix type arising in the the harmonic analysis on the infinite symmetric group.

Back

Polyhedra in the Bible: Two geometric puzzles
Ron Livne, Hebrew University

Abstract: The Book of Numbers, Bamidbar, opens with the census of the Tribes of Israel. We will show that the numbers of the tribes encode a geometric puzzle - an arrangement based on a tetrahedron embedded in a cube embedded in a dodecahedron, all with common vertices. We shall likewise show that in the  Book of Genesis, the ages of the patriarchs when their successor was born encode a  second geometric puzzle, based on a Hamiltonian path on a dodecahedron or even more aesthetically, on an archimedean solid named icosi-dodecahedron.

The talk will continue the Colloquium talk that will be given on the same day, and attending the Colloquium would be helpful although not logically necessary. We will try to show that these bizarre-looking mathematical connections are actually meaningful. In fact these connections appear to cast some light on the evolution of the different versions of the Torah.

Back

An application of group characters to a problem in approximation theory
Michael Schein, Bar-Ilan University

Abstract: Suppose that we are given a function f that is known to lie in a predetermined n-dimensional space of functions.  Measuring the value of f at any n distinct points will, generically, provide enough information to determine the function.  Suppose that, as in the real world, there are errors of measurement: repeated evaluation of f at a given point gives rise to a distribution of values. A choice of n points is called an optimal design if it minimizes the number of measurements necessary to determine f to a specified degree of confidence.

We will show how some basic facts about the character theory of finite groups may be used to obtain results about optimal designs in some situations where symmetries are present.  As a particular case of our work, we find a short proof of a theorem of Lee from 1984 about minimality of B-splines.  We will discuss other problems to which our method may be applicable.  Comments and questions from the audience are actively solicited.

Back

Lower bounds for designs in symmetric spaces
Alex Samorodnitsky, Hebrew University

Abstract: A design is a (finite) subset of points in a space on which simple functions ("low-degree polynomials") average to their total average. Examples of designs in different spaces are orthogonal arrays, block designs, and spherical designs.

We will consider nice spaces ('nice' means graphs and Riemannian manifolds with many symmetries) and prove the following geometric claim:  a design has to be large, because a union of "spheres" around its points "covers" the whole space.

As an application, we recover "linear programming" lower bounds on the cardinality of designs in most known (and possibly some new) cases.

Back

Lie superalgebras and some characters of S_n
Amitai Regev, Weizmann Institute of Science

Abstract: We prove a formula for S_n characters which are indexed by the partitions in the (k,\ell) hook. The proof applies a combinatorial part of the theory of Lie superalgebras.

Back

Axioms for the Griess algebra
Sergey Shpectorov, Birmingham University

Abstract: The Griess algebra is the 196884-dimensional real commutative non-associative algebra whose automorphism group is the Monster sporadic simple group M. Based on the work on Miyamoto and Sakuma, Ivanov proposed a set of axioms for a class of algebras  he called Majorana algebras.

In the talk we will review these developments and discuss a possible relaxation of the axioms leading to the concept of the universal k-generated Majorana algebra. Sakuma's theorem can then be interpreted as the result on the finiteness of the universal 2-generated Majorana algebra. We will conclude with some ideas how combinatorics can be used for these and further results.

Back

Higher, weaker (and maybe faster) orders on words and trees
Yuval Roichman, Bar-Ilan University

Abstract: The higher Bruhat order was introduced by Manin and Schechtman and later studied by Felsner, Ziegler, B&M Shapiro, Vainshtein and others. In this talk we consider two related posets: the first is a "weak" analogue, and the other is determined by a braid group action on labelled trees and words. Properties of these posets and connections to (q,t)-Catalan numbers will be discussed. Applications to evaluations of distances between reduced words will be presented.

Based on joint works with Vic Reiner and Ron Adin.

Back

Treewidth reduction theorem and algorithmic problems on graphs
Igor Razgon, University of Leicester

Abstract: We introduce the so called treewidth reduction theorem. Given a graph $G$, two specified vertices $s$ and $t$, and an integer $k$, let $C$ be the union of all minimal $s-t$ (vertex) separators of size at most $k$. Further on, let $G^*$ be the graph obtained from $G$ by contracting all the connected components of $G \setminus C$ into single vertices. The theorem states that the treewidth of $G^*$ is bounded by a function of $k$ and that the graph $G^*$ can be computed in a linear time for any fixed $k$.

The above theorem allows us to solve in a linear time for every fixed $k$ the following generic graph separation problem. Let $G$ be a graph with two specified vertices $s$ and $t$ and let $Z$ be a hereditary class of graphs. The problem asks if $G$ has a $s-t$ vertex separator of size at most $k$ such that the subgraph graph induced by $S$ belongs to the class $Z$.

In other words, we show that this generic problem is fixed-parameter tractable. This allows us to resolve a number of seemingly unrelated open questions scattered in the literature concerning fixed-parameter tractability of various graph separation problems under specific constraints.

The role of the treewidth reduction theorem is that it reduces an arbitrary instance of the given problem to an instance of the problem where the treewidth is bounded. Then a standard methodology using Courcelle's theorem can be applied.

The purpose of this talk is to convey the main technical ideas of the above work in an intuitive level. The talk is self-contained. In particular, no prior knowledge of parameterized complexity, treewidth, and Courcelle theorem is needed. Everything will be intuitively defined in the first 10-15 minutes of the talk.

Joint work with D. Marx and B. O'Sullivan. Available at http://arxiv.org/abs/1110.4765

Back

Locally testable codes and expanders
Tali Kaufman, Bar-Ilan University

Abstract: Expanders and error correcting codes are two celebrated notions, coupled together, e.g., in the seminal work on Expander Codes by Sipser and Spielman that yields some of the best codes. Recently, there is a growing interest in codes admitting algorithms that run in *constant* time, e.g., codes for which it is possible to distinguish in constant time between codewords and vectors far from the code. Such codes are known as locally testable codes (LTCs).

It is known that Expander Codes based on *best* expanders can NOT yield LTCs, so it seems that expansion is somewhat contradicting to the notion of LTCs. We show that, nevertheless, the graph associated with an LTC *must* be essentially an expander. Namely, this graph is a small set expander and it can be decomposed into constant many expander graphs on which the induced codes are approximately LTCs.

Based on joint work with Irit Dinur.

Back

Arithmetic groups, Ramanujan graphs and error correcting codes
Alex Lubotzky, Hebrew University

Abstract: While many of the classical codes are cyclic, a long standing conjecture asserts that there are no "good" cyclic codes. In recent years, interest in symmetric codes has been stimulated by Kaufman, Sudan, Wigderson and others (where symmetric means that the acting group can be any group). Answering their main question (and contrary to common expectation), we show that there DO exist symmetric good codes. In fact, our codes satisfy all the "golden standards" of coding theory. Our construction is based on the Ramanujan graphs constructed by Lubotzky-Samuels-Vishne as a special case of Ramanujan complexes. The crucial point is that these graphs are edge transitive and not just vertex transitive as in previous constructions of Ramanujan graphs. These complexes are obtained as quotients of the Bruhat-Tits building modulo the action of suitable arithmetic groups. We will discuss the potential of these complexes and their cohomology to yield more applications to coding theory.

All notions will be explained.

Joint work with Tali Kaufman.

Back

New product formulas for tableaux
Ron Adin, Bar-Ilan University

Abstract: Product formulas for the number of Standard Young Tableaux have long been known for two families of shapes - regular and shifted. We present an unexpected addition to this list, consisting of truncated shapes. Parallel results have been obtained by G. Panova (Harvard).

Joint work with Ronald King and Yuval Roichman.

Back

Strongly regular graphs with no triangles: Challenges and computer algebra results
Matan Ziv-Av, Ben-Gurion University

Abstract: A strongly regular graph (briefly SRG) with parameters (v,k,\lambda,\mu) is a regular graph of valency k such that every two neighbours have exactly \lambda common neighbours, and every two non-neighbours have exactly \mu common neighbours.  An SRG is called primitive if both the graph and its complement are connected.

We consider primitive SRGs with no triangles (that is \lambda=0, briefly called tfSRGs). The most famous SRG with no triangles, denoted by NL_2(10), has parameters (100, 22, 0, 6). It was described in a paper by Higman and Sims in 1968 in the course of the discovery of a new sporadic simple group HS. Twelve years earlier, Dale Mesner Constructed this graph, Denoting it by NL_2(10). Mesner constructed NL_2(10) by way of an equitable partition of this graph.

This construction raises two enumeration problems relating to tfSRGs. One is embedding smaller tfSRGs in larger ones, and the other is equitable paritions of tfSRGS. We present complete computer aided enumeration of embeddings of tfSRGs inside known tfSRGs, and computer aided emumeration of equitable partitions of tfSRG of size up to 50.

Back