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/λ₁ 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²) 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₃s). Erdos conjectured that this was also true of monochromatic copies of K₄, 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.