Titles and abstracts for invited talks at the 2005 BCC

Speaker: Ben Green

Title: Finite field models in additive combinatorics

The study of many problems in additive combinatorics, such as Szemerédi's theorem on arithmetic progressions, is made easier by first studying models for the problem in F_p ⁿ    for some fixed small prime p. We give a number of examples of finite field models of this type, which allows us to introduce some of the central ideas in additive combinatorics relatively cleanly. We also give an indication of how the intuition gained from the study of finite field models can be helpful for addressing the original questions.
 

Speaker: Oliver King

Title: The subgroup structure of finite classical groups in terms of geometric configurations
 

L.E.Dickson's approach to the subgroups of PSL₂(q) (the Linear Fractional Group) gives rise to a description of subgroups as fixing one of: a real point; a pair of real points; a pair of imaginary points; a sub-line; and so on. H.H. Mitchell took a similar approach in describing subgroups of PSL₃(q) and PSp₄(q) (for odd q). In the 1980s, Aschbacher gave a description of subgroups of classical groups as either lying in one of eight classes or being almost simple; the eight classes can largely be described geometrically. The remaining subgroups have not yet been completely determined but a certain amount of geometric structure can be identified. Our paper gives a survey of progress towards a geometric description of subgroups of the classical groups.
 

Speaker: Patric Östergård

Title: Constructing combinatorial objects via cliques
 
Many fundamental combinatorial objects, including balanced incomplete block designs and error-correcting codes, can be constructed and classified via cliques in certain problem-specific graphs. Various such objects are here identified and surveyed, and the utilization of clique algorithms in the construction of these is considered. Occasionally the type of problem admits a formulation as an instance of the exact cover problem, which, for computational reasons, is even more desirable.
 

Speaker: Tim Penttila

Title: Flocks of circle planes

Flocks of finite circle planes - inversive, Minkowski and Laguerre planes - are surveyed, including their connections with projective planes, generalised quadrangles and ovals.
 

Speaker: Alex Scott

Title: Judicious partitions and related problems

Many classical partitioning problems in combinatorics ask for a single quantity to be maximized or minimized over a set of partitions of a combinatorial object.  For instance, Max Cut asks for the largest bipartite subgraph of a graph G, while Max Bisection asks for the minimum size of a cut into two equal pieces.

In this survey we shall be concerned with judicious partitioning problems, in which we seek to maximize or minimize a number of quantities simultaneously.  For instance, given a graph with m edges, we can ask for the smallest  f(m) such that G must have a bipartition in which each vertex class contains at most  f(m) edges.

We shall survey recent work by a number of authors on a variety of problems involving judicious partitions and related properties, from both an extremal and an algorithmic perspective, as well as stating some new results and a number of open questions.
 

Speaker: Oriol Serra

Title: An isoperimetric method for the small sumset problem

We survey applications of an isoperimetric method to the small sumset problem in Additive Theory. The small sumset problem asks for lower bounds of the cardinality of the sum of two sets in a group. Sample proofs are presented to illustrate the application of the method, which is based on connectivity properties of graphs. In the final part we describe some applications to several problems in number theory, group theory and combinatorics.
 

Speaker:  Paul Seymour (Co-author: Maria Chudnovsky)

Title: The structure of claw-free graphs

A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. At first sight, there seem to be a great variety of types of claw-free graphs. For instance, there are line graphs, the graph of the icosahedron, complements of triangle-free graphs, and the Schläfli graph (an amazingly highly-symmetric graph with 27 vertices), and more; for instance, if we arrange vertices in a circle, choose some intervals from the circle, and make the vertices in each interval adjacent to each other, the graph we produce is claw-free.  There are several other such examples, which we regard as ``basic'' claw-free graphs. Nevertheless, it is possible to prove a complete structure theorem for claw-free graphs. We have shown that every connected claw-free graph can be obtained from one of the basic claw-free graphs by simple expansion operations. In our paper we explain the precise statement of the theorem, sketch the proof, and give a few applications.

Speaker: Alan Sokal

Title: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids

The multivariate Tutte polynomial (known to physicists as the Potts-model partition function) can be defined on an arbitrary finite graph G, or more generally on an arbitrary matroid M,  and encodes much important combinatorial information about the graph (indeed, in the matroid case it encodes the full structure of the matroid).  It contains as a special case the familiar two-variable Tutte polynomial --- and therefore also its one-variable specializations such as the chromatic polynomial, the flow polynomial and the reliability polynomial --- but is considerably more flexible. I begin by giving an introduction to all these problems, stressing the advantages of working with the multivariate version. I then discuss some questions concerning the complex zeros of the multivariate Tutte polynomial, along with their physical interpretations in statistical mechanics (in connection with the Yang--Lee approach to phase transitions) and electrical circuit theory. Along the way I mention numerous open problems. This survey is intended to be understandable to mathematicians with no prior knowledge of physics.
 

Speaker: Angelika Steger

Title: The sparse regularity lemma and its applications

Szemerédi's regularity lemma is one of the most celebrated results in modern graph theory. However, in its original setting it is only helpful for studying large dense graphs, that is, graphs with n vertices and Θ(n²) edges. The main reason for this is that the underlying concept of ε-regularity is not meaningful when dealing with sparse graphs, since for large enough n every graph with o(n²) edges is ε-regular. In 1997 Kohayakawa and Rödl independently introduced a modified definition of ε-regularity which is also useful for sparse graphs, and used it to prove an analogue of Szemerédi's regularity lemma for sparse graphs. However, some of the key tools for the application of the regularity lemma in the dense setting, the so-called embedding lemmas or, in their stronger forms,  counting lemmas, are not known to be true in the sparse setting. In fact, counterexamples show that these lemmas do not always hold. However, Kohayakawa, Łuczak, and Rödl formulated a probabilistic embedding lemma that, if true, would solve several long-standing open problems in random graph theory. In this survey we give an introduction to Szemerédi's regularity lemma and its generalisation to the sparse setting, describe embedding lemmas and their applications, and discuss recent progress towards a proof of the probabilistic embedding lemma. In particular, we present various properties of ε-regular graphs in the sparse setting. We also show how to use these results to prove a weak version of the conjectured probabilistic embedding lemma.

 

Send mail to M.J.Grannell@open.ac.uk with questions or comments about this web site.
Last modified: 27/07/05