Abstracts

Upper bounds on the number of Steiner triple systems and 1-factorizations
Zur Luria, Hebrew University

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

Back

On flag f-vectors of Gorenstein* posets
Eran Nevo, Ben-Gurion University

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

Back

Hindman's coloring theorem in arbitrary semigroups
Gili Golan, Bar-Ilan University

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

Back

Enumeration of strongly regular designs
Sven Reichard, Essen and Ben-Gurion University

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

Back

The width of the perfect matching graph for knots
Moshe Cohen, Bar-Ilan University

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

Back

Simple spanning trees in geometric graphs
Chaya Keller, Hebrew University

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

Note: The talk will be given in Hebrew.

Back

Winning fast in Maker-Breaker games played on sparse random boards
Asaf Ferber, Tel-Aviv University

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

Back

Four infinite families of non-Schurian association schemes of order 2p^2
Stefan Gyurki, Ben-Gurion University, Beer Sheva, and Slovak University of Technology, Bratislava

Abstract: Association schemes form one of the traditional areas of investigations in algebraic graph theory. Catalogues of all small 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 only two examples of non-Schurian association schemes of order 18.

Starting from a successful computer-free interpretation of these two examples, and using extensive computer algebra experimentation in conjunction with further reasoning, we were able to show the existence of at least four infinite families of non-Schurian association schemes of order 2p^2 (for p prime, p>3).

In this lecture I will start from a consideration of the two initial examples on 18 points, and describe some auxiliary coherent configurations. Then the four infinite families of association schemes will be presented. We will discuss some of their properties, as well as their links with certain known objects in extremal graph theory.

This is joint work with M. Klin.

Back

Positional games
Michael Krivelevich, Tel Aviv University

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

Back

From joints to distinct distances and beyond: The dawn of an algebraic era in combinatorial geometry
Micha Sharir, Tel-Aviv University

Abstract: In November 2010 the earth has shaken, when Larry Guth and Nets Hawk Katz posted a nearly complete solution to the distinct distances problem of Erd{\H o}s, open since 1946. The excitement was twofold: (a) The problem was one of the most famous problems, as well as one of the hardest nuts in the area, resisting solution in spite of many attempts (which only produced partial improvements). (b) The proof techniques were algebraic in nature, drastically different from anything tried before.

The distinct distances problem is to show that any set of n points in the plane determine Omega(n/\sqrt{\log n}) distinct distances. (Erd{\H o}s showed that the grid attains this bound.) Guth and Katz obtained the lower bound Omega(n/\log n).

Algebraic techniques of this nature were introduced into combinatorial geometry in 2008, by the same pair Guth and Katz. At that time they gave a complete solution to another (less major) problem, the so-called joints problem, posed by myself and others back in 1992. Since then these techniques have led to several other developments, including an attempt, by Elekes and myself, to reduce the distinct distances problem to an incidence problem between points and lines in 3-space. Guth and Katz used this reduction and gave a complete solution to the reduced problem.

One of the old-new tools that Guth and Katz bring to bear is the Polynomial Ham Sandwich Cut, due to Stone and Tukey (1942). I will discuss this tool, including a ``1-line'' proof thereof, and its applications in geometry, as they are slowly emerging during the past year and a half.

In the talk I will review all these developments, as time will permit. Only very elementary background in algebra and geometry will be assumed.

Back

Semicharacters of groups
Gil Alon, Open University

Abstract: We consider the notion of a semicharacter of a finite group G: It is a function from G to C*, whose restriction to any abelian subgroup is a homomorphism. The set of semicharacters of G is a finite abelian group, that we denote by \hat{G}. This notion extends the notion of the Dual group of an abelian group. However, for a nonabelian group G, it is not obvious that \hat{G} is nontrivial. We will prove it; the proof depends on the classification of finite simple groups.

We conjecture that the order of \hat{G} is always divisible by the order of G. This conjecture is supported by numerical evidence : We have verified it for all groups of size less than 256. We will show that the conjecture holds for some central families of groups (including the General Linear, Symmetric and Alternating groups), using some "hands on" constructions, that rely heavily on the structure of the given group.

Back

Compression methods and sums of sets in (Z_2)^n
Chaim Even-Zohar, Hebrew University

Abstract: Denote by F(K) the maximum of |span(A)|/|A|, over all subsets A of (Z_2)^n with |A+A|/|A| < K. Using methods of subset compression, Green and Tao and Konyagin found F(K) = Theta( poly(K) 4^K ). Elaborating on these methods, we explicitly calculate F(K), and in particular show that it is Theta( 4^K / K ). More generally, we give a fairly tight lower bound on |A+B|, where A and B are two generating subsets of (Z_2)^n of prescribed cardinalities.

Back