# Program

Monday | Tuesday | Wednesday | |

9:30-10:30 | Noga Alon |
David Ellis |
Balázs Szegedy |

10:30-11:00 | Coffee Break |
Coffee Break |
Coffee Break |

11:00-12:00 | Wojciech Samotij |
Julia Wolf |
Keith Ball |

12:00-14:00 | Lunch |
Lunch |
Lunch |

14:00-14:40 | Jan Hladky |
Oliver Kullmann |
Shiping Liu |

14:40-15:20 | Ivan Izmestiev |
Malgorzata Bednarska-Bzdega |
Evan DeCorte |

15:20-15:50 | Coffee Break |
Coffee Break |
Coffee Break |

15:50-16:30 | Joonkyung Lee |
Bartlomiej Bzdega |
Polyxeni Lamprou |

16:30-17:10 | Matthew Jenssen |
Orit Raz |
Mykhailo Zarichnyi |

17:30- | Reception & dinner | Dinner | Dinner |

All talks are in B3.02. Lunches/dinners/coffee breaks are in the Common Room (1st floor).

## Abstracts

**Noga Alon **(Tel-Aviv)

Neither combinatorial nor constructive combinatorics

Abstract:

I will describe several old and new applications of topological and algebraic methods

in the derivation of combinatorial results. In all of them the proofs provide no efficient solutions

for the corresponding algorithmic problems.

**Keith Ball **(Warwick)

*A sharp combinatorial version of Vaaler's and Minkowski's Theorems*

Abstract:

We explain a new method for locating long vectors in convex domains which is part

analytic and part combinatorial. The main argument consists of a sequence of linked optimisation

problems. (Joint work with M. Prodromou.)

**Malgorzata Bednarska-Bzdega **(Adam Mickiewicz University, Poznan)

*Number theory problems in combinatorial games*

Abstract:

Let X be a finite set, be a family of subsets of X and

let a,b be positive integers. In the Avoider-Enforcer game in each round

Avoider selects exactly a free elements of X and Enforces answers by

selecting exactly b free elements of X. The game ends when there is no

free element left. Enforcer tries to force Avoider to select all elements of

at least one set from . It appears that the result of the game

depends often on the remainder of the division of X by a+b. I will talk

on two number theory problems arising in the context of such games.

**Bartlomiej Bzdega **(Adam Mickiewicz University, Poznan)

*On coefficients of cyclotomic polynomials*

Abstract:

We present an upper bound on coefficients

of cyclotomic polynomials Φ_{n}, where the number

ω=ω(n) of distinct primes dividing n is

fixed. In our proof we use basic combinatorial tools

such that Sperner's Theorem. Additionally we describe

a connection between cyclotomic coefficients and lattice

points in some simplices, especially for the case ω=3.

**Evan DeCorte **(Hebrew University of Jerusalem)

*Maximum independent sets in the orthogonality graph*

Abstract:

The orthogonality graph is the graph whose vertex set is the

unit sphere in , in which two vectors are joined with an edge when

they are orthogonal. Witsenhausen in 1974 asked for the largest possible

fraction of the sphere which can be occupied by a Lebesgue measurable

independent set in the orthogonality graph, and he gave the upper bound

of 1/3. We improve this upper bound to 0.313 using an approach inspired

by the Delsarte bounds for codes, combined with some combinatorial reasoning.

This is the first progress on the Witsenhausen problem in dimension 3 since

the original statement of the problem. Joint work with Oleg Pikhurko.

**David Ellis **(Queen Mary University of London)

*Some applications of non-Abelian Fourier analysis in Combinatorics
*Abstract:

We discuss some problems in extremal combinatorics which have been tackled in the last few years with the aid of non-Abelian Fourier analysis. These include Gowers’ disproof of the Babai-Sós conjecture on product-free subsets of groups, a proof of the Deza-Frankl conjecture on t-intersecting families of permutations, some forbidden intersection problems for permutations, and some isoperimetric problems for the symmetric group. We also discuss some related open problems. Partly based on joint work with Yuval Filmus, Ehud Friedgut and Haran Pilpel.

**Jan Hladky **(Czech Academy of Sciences, Prague)

*f-vectors of flag complexes*

Abstract:

An f-vector is an enumeration of faces of all dimensions of a

given geometric object. So, for example the f-vector of a 3-cube is (8,12,6)

as it has 8 vertices, 12 edges, and 6 sides. f-vectors and its relatives

(called gamma- and h-vectors) are central objects of study in geometric

combinatorics. What f-vectors can be attained by a given class of geometric

objects? Or, can we at least get upper bounds for face numbers of a given

dimension (“upper-bound theorems”). With Michal Adamaszek (Copenhagen) we

applied methods from extremal graph theory and got an optimal upper-bound

theorem for flag triangulations of manifolds of odd dimension. I will explain

the connection. Only basic graph theory (Euler's formula) will be assumed,

otherwise the talk will be self-contained.

* *

**Ivan Izmestiev **(Free University, Berlin)

*Impossible triangulations*

Abstract:

If a triangulation of the sphere has only two vertices of odd degree, then these

cannot be adjacent. We prove this fact by studying the coloring monodromy, an

obstruction to the existence of a vertex coloring. Similar, but also different

is the following theorem. There is no triangulation of the torus with all vertex

degrees 6, except for one of degree 5 and one of degree 7. This is proved by studying

the rotation monodromy of the geometric structure obtained by making each triangle

of the triangulation to an equilateral euclidean triangle.

The second result is a joint work with Kusner, Rote, Springborn, and Sullivan.

** **

**Matthew Jenssen **(LSE)

*The Multicolour Ramsey Number of a Long Odd Cycle*

Abstract:

For a graph G, the k-colour Ramsey number R_{k}(G) is the least integer

N such that every k-colouring of the edges of the complete graph K_{N} contains

a monochromatic copy of G. Let C_{n} denote the cycle on n vertices.

We show that for fixed k≥3 and n odd and sufficiently large, R_{k}(C_{n})=2^{k-1}(n-1)+1.

This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a

conjecture of Bondy and Erdös for large n. We also establish a surprising

correspondence between extremal k-colourings for this problem and perfect matchings

in the hypercube Q_{k}. This allows us to in fact prove a stability-type generalisation

of the above. The proof is analytic in nature, the first step of which is to use the

Regularity Lemma to relate this problem in Ramsey Theory to one in Convex Optimisation.

** **

**Oliver Kullmann **(Swansea)

*SAT, Extremal Combinatorics, and elementary Number Theory*

Abstract:

At least amongst computer scientists it is well-known that progress over the

last 15 years in SAT, the decision problem whether a propositional formula is

satisfiable, has dramatically changed industrial applications in the area of

verification of hardware and software. It is also well-known that SAT is

likely the best tool available to tackle concrete combinatorial instances,

coming for example from Ramsey theory. On the theory side, connections to

random structures and to complexity theory are prominent. We consider here a

less well-known stream of research, which can be understood as part of the

general quest of “understanding unsatisfiability” (where we believe that

this is possible).

More precisely, we are investigating ``minimally unsatisfiable'' clause-sets

(MUs for short), where, as with critically colourable hypergraphs,

unsatisfiability is destroyed by removing any clause (“condition”). See [2]

for a general overview, and see especially the introduction of [3] for the

connections to combinatorics.

Since the fundamental work [1] by Aharoni and Linial, it is known that such

MUs must have at least one more clause than variables, and this is known

nowadays as deficiency delta ≥1, where

delta = number of clauses - number of variables.

The great goal is the finiteness conjecture, which states that for bounded

deficiency k there are only finitely many MU-“patterns”.

A step towards this is determining extremal parameter values in delta,

like degrees of variables and the number of “full clauses”, which are clauses

containing all variables. In terms of covers of the boolean hypercube by

subcubes, where “MU” means irredundant (or minimal) cover, full clauses

correspond to singleton sub-cubes.

After a general introduction, I will present the results of our latest work

[4], which gives a lower bound on the maximal number of full clauses, and

introduces connections to elementary number theory and recursion schemes

(meta-Fibonacci sequences).

**[1]** http://www.sciencedirect.com/science/article/pii/0097316586900609

Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas

Ron Aharoni, Nathan Linial

**[2]** http://cs.swan.ac.uk/~csoliver/papers.html\#Handbook2009MUAUT

Minimal Unsatisfiability and Autarkies

Hans Kleine Buening, Oliver Kullmann

Chapter 11 of Handbook of Satisfiability

**[3]** http://arxiv.org/abs/1408.0629v1

Bounds for variables with few occurrences in conjunctive normal forms

Oliver Kullmann, Xishun Zhao

**[4]** http://arxiv.org/abs/1505.02318

Parameters for minimal unsatisfiability: Smarandache primitive numbers and full clauses

Oliver Kullmann, Xishun Zhao

**Polyxeni** **Lamprou **(Weizmann Institute)

*A new interpretation of Catalan numbers*

Abstract:

The Catalan numbers form a sequence of integers; for all

natural number t the t-th Catalan number is given by the formula

A collection of sets H__{t} such that |H_{t}| = C_{t} for all t is called a Catalan

set. Many examples of Catalan sets are known; the triangulations of

the (t + 2)-gon, the Dyck paths from (0, 0) to (0, 2t) and the nilpotent

ideals in the Borel subalgebra of to name but a few. In Stanley's

book “Enumerative Combinatorics”, one can find 66 examples of Catalan

sets and a few more in his “Catalan addendum”.

In my talk I will present a new example of a Catalan set, which has

a remarkable property: for all t, H_{t} decomposes into a (non-disjoint)

union of (almost) (t - 1)! subsets each of cardinality 2^{t-1}. Moreover,

one may define some interesting graphs for H^{t} and its subsets.

The above results were obtained while studying the additive structure

of the Kashiwara crystal B(∞) and are a joint with A. Joseph and

S. Zelikson.

**Joonkyung** **Lee **(Oxford)

*Some Advances on Sidorenko's Conjecture*

Abstract:

A bipartite graph H is said to have Sidorenko's property if the probability

that the uniform random mapping from V(H) to the vertex set of any graph

G is a homomorphism is at least the product of the probabilities that each

edge of H is mapped into an edge in G. In this talk, I will give an overview of

the known results and new approaches to attack Sidorenko’s conjecture. This

is joint work with David Conlon, Jeong Han Kim, and Choongbum Lee.

**Shiping Liu **(Durham)

*Cheeger constant, spectral clustering and eigenvalue ratios of Laplacian*

Abstract:

Cheeger inequality is a fundamental result in spectral geometry

of Riemannian manifolds and graphs. Recently, based on empirical intuitions

of the spectral clustering algorithm, Kwok et al. proved an improved version

of it. In this talk, we will transfer this improved Cheeger inequality to the

setting of a closed Riemannian manifold, and combine it with a spectral estimates

depending on Ricci curvature due to Buser, to derive an optimal dimension-free

upper bound estimate for eigenvalue ratios λ_{k}/λ_{1} of the Laplacian

on manifolds with nonnegative Ricci curvature. This result answers open questions

of Funano and Shioya. The idea around Ricci curvature can be brought into the

combinatorial world via Bakry and Emery's Γ-calculus. Graphs satisfying

the inequality CD(0,∞) is analogous to Riemannian manifolds possessing

nonnegative Ricci curvature. This leads us to an analogous eigenvalue ratio

estimates for finite graphs, which is independent of the graph size. We show

that the condition CD(0,∞) “tensorizes”. Hence we have many graphs satisfying

the curvature condition. The size independent feature of our eigenvalue ratio estimate

makes it useful for the discussion of (multi-way) expanders. in particular, we will

show a ratio estimate of the multi-way Cheeger constants of finite graphs.

This is partially joint work with Norbert Peyerimhoff.

**Orit Raz **(Tel-Aviv)

*Polynomials vanishing on Cartesian products*

Abstract:

Let F(x,y,z) be a real trivariate polynomial of constant degree, and let A,B,C be three

sets of real numbers, each of size n. How many roots can F have on A x B x C?

This question has been studied by Elekes and Rónyai and then by Elekes and Szabó about 15 years ago.

One of their striking results is that, for the special case where F(x,y,z) = z-f(x,y), either F vanishes

at o(n^{2}) number of points of A x B x C, or else f must have one of the special forms

f(x,y) = h(p(x)+q(y)) or f(x,y) = h(p(x)q(y)), for univariate polynomials p, q, h.

In the talk I will discuss several recent results, in which the analysis is greatly simplified, and the

bounds become sharp: If F does not have a special form, the number of roots is at most O(n^{11/6}). The

results also hold over the complex field.

This setup arises in various Erdös-type problems in combinatorial geometry, and the result provides a

unified tool for their analysis. I will discuss several applications of this kind.

The proofs use techniques from algebra and algebraic geometry, and can be viewed as part of the recent

growing body of works on algebraic techniques for combinatorial geometry problems.

Joint work with Micha Sharir, Jozsef Solymosi, and Frank de Zeeuw.

**Wojciech Samotij **(Tel-Aviv)

*The structure of a random metric space*

Abstract: What does a typical metric space on n points look like? To formalise

this question, we consider the set of all metric spaces on n points whose

diameter is at most 2. Viewing every metric space as a vector of

distances, this set becomes a convex polytope in , the so-called

“metric polytope”. A random metric space is then a space chosen according to

the normalised Lebesgue measure on this polytope. It is easy to see that the

metric polytope contains the cube . Our main result

is that it does not contain much more. Precisely, we show that a random

metric space is very rigid, having all distances in an interval of the form

[1-n^{-ε}, 2] with high probability.

Joint work with Gady Kozma, Tom Meyerovitch, and Ron Peled.

**Balázs Szegedy **(Rényi Institute, Budapest)

*The information theoretic approach to Sidorenko's conjecture and sparse graph limits*

Abstract:

Sidorenko's famous conjecture says that the density of a bipartite graph H in any other graph G is at least the edge density of G raised to the power |E(H)|. The conjecture has several equivalent formulations in different fields of Mathematics. We present new results that are based on an information theoretic approach. As a byproduct we develop a limit concept for sparse graphs and another related information theoretic limit concept.

**Julia Wolf **(Bristol)

* Counting monochromatic structures in finite abelian groups*

Abstract:

It is well known (and a result of Goodman) that a random 2-colouring of the edges of the complete graph K_{n} contains asymptotically the minimum number of monochromatic triangles (K_{3}s). Erdos conjectured that this was also true of monochromatic copies of K_{4}, but his conjecture was disproved by Thomason in 1989. The question of determining for which small graphs Goodman’s result holds true remains wide open.

We explore an arithmetic analogue of this question: what can be said about the number of monochromatic additive configurations in 2-colourings of finite abelian groups? The techniques used to address this question, which include additive combinatorics and quadratic Fourier analysis, originate in quantitative approaches to Szemeredi’s theorem. Perhaps surprisingly, some of our results in the arithmetic setting have implications for the original graph-theoretic problem.

**Mykhailo Zarichnyi **(L'viv State University)

*Asymptotic Dimension and Finite Decomposition Complexity*

Abstract:

The coarse geometry deals with large scale properties of metric spaces

and, more generally, coarse spaces. The asymptotic dimension (Gromov)

and finite decomposition complexity (Guentner, Tessera, Yu) are

examples of large scale invariants. The talk will be devoted to

combinatorial components of these invariants.