## School Starts at HUJI

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 $R^n$ 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 $r(K_s,Q_n)$ is the smallest positive integer N
such that every red-blue colouring of the edges of the complete graph
$K_N$ 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 $r(K_s,Q_n)=(s-1)(2^{n}-1)+1$ 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.