We are now starting the third week of the academic year at HUJI. As usual, things are very hectic, a lot of activities in the mathematics department, in our sister CS department, around in the campus, and in our combinatorics group. A lot is also happening in other universities around. This semester I am teaching a course on “Social Choice and some Topics from Cooperative Game Theory” in our Federmann Center for the Study of Rationality. I will probably create a page for the course in the near future. During the summer we ran an informal multi-university research activity on analysis of Boolean functions where for two months we met every week for a whole day. I will try to report on what we were studying and we will probably meet during the academic year 2-3 times each semester.

A few of many future events: Later this month we will have here a cozy Polish-Israeli meeting on topological combinatorics, on December we will celebrate Ilya Rips 65 birthday with a conference on geometric and combinatorial group theory, and at the last two weeks of January our traditional The 18th yearly midrasha (school) in mathematics that will be devoted to combinatorics with six lecture series and a few additional talks aimed at teaching some of the very latest exciting developments. If you did not register yet to the Midrasha, please go ahead and do so. This can be a very nice opportunity to visit Israel and learn some exciting combinatorics and to meet people. Partial support for travel and local expenses is available.

COMBSEM – weeks I, II, III

Our weekly combinatorics seminar is meeting on Mondays 9-11. Let me tell you a little on what we had in the first two weeks and what is planned for the third.

Week I: A startling extension of the associahedron

Monday, October 27, 11:00–13:00, at room B221 in Rothberg building

(new CS and engineering building).

**Speaker: Jean-Philippe Labbé, HU**

**Title: A construction of complete multiassociahedric fans**

Abstract:

Originally, Coxeter groups emerged as an algebraic abstraction of

groups generated by reflections in a vector space. The relative

generality of their definition allows them to be related to many

combinatorial, geometric and algebraic objects. This talk show cases

recent developments in the study of a family of simplicial spheres

describing multi-triangulations of convex polygons based on

combinatorial aspects of Coxeter groups of type A. This family of

simplicial spheres generalizes the associahedra. A conjecture of

Jonsson (2003) asserts that these simplicial spheres can be realized

geometrically as the boundary complex of a convex polygon, that would

be thus called *multiassociahedron*. We will describe a

construction method to obtain complete simplicial fans realizing an

infinite non-trivial family of multi-associahedra. At it turned out, Jonsson’s conjecture is closely related to a conjecture by Miller and Knudson.

This is joint work with Nantel Bergeron and Cesar Ceballos (Fields

Institute and York Univ.).

Week II: Finally, progress on Withenhausen’s problem in 2 dimension

**Speaker: Evan deCorte, HU**

**Title: Spherical sets avoiding a prescribed set of angles**

Abstract: Let X be any subset of the interval [-1,1]. A subset I of

the unit sphere in will be called X-avoiding if <u,v> is not in X

for any u,v in I. The problem of determining the maximum surface

measure of a {0}-avoiding set was first stated in a 1974 note by H.S.

Witsenhausen; there the upper bound of 1/n times the surface measure

of the sphere is derived from a simple averaging argument. A

consequence of the Frankl-Wilson theorem is that this fraction

decreases exponentially, but until now the 1/3 upper bound for the

case n=3 has not moved. We improve this bound to 0.313 using an

approach inspired by Delsarte’s linear programming bounds for codes,

combined with some combinatorial reasoning. In the second half of the

talk, we turn our attention to the following question: Does there

exist an X-avoiding subset of the unit sphere maximizing the surface

measure among all X-avoiding subsets? (Or could there be a supremum

measure which is never attained as a maximum?) Using a combination of

harmonic and functional analysis, we show that a maximizer must exist

when n is at least 3, regardless of X. When n=2, the existence of a

maximizer depends on X; sometimes it exists, sometimes it does not.

This is joint work with Oleg Pikhurko.

Week III (coming up tommorow): Ramsey numbers for cliques vs cubes conquered at last!

**Speaker: Gonzalo Fiz Pontiveros, HU**

** Title: The Ramsey number of the clique and the hypercube**

Abstract:

The Ramsey number is the smallest positive integer N

such that every red-blue colouring of the edges of the complete graph

on N vertices contains either a red n-dimensional hypercube,

or a blue clique on s vertices. It was conjectured in 1983 by

Erdos and Burr that for every

positive integer s and every sufficiently large n. The aim of the

talk is to give an overview of the proof of this result and, if time

allows it, discuss some related problems.

Joint work with S. Griffiths, R.Morris, D.Saxton and J.Skokan.