Invited talks will be given by:
Arrigo Bonisoli (Università di Modena e Reggio Emilia, Italy):
Graph decompositions and symmetry
Peter J Cameron (Queen Mary, University of London, UK):
Optimal block designs for combinatorialists
Willem H Haemers (Tilburg University, The Netherlands):
Structure and spectra of graphs
Gholamreza B Khosrovshahi (IPM, Iran):
Trades and t-designs
Alexandr V Kostochka (University of Illinois at Urbana-Champaign, USA):
Extremal graph packing problems: Ore-type versus Dirac-type
Daniela Kühn (University of Birmingham, UK):
Embedding large graphs into dense graphs
Marc Noy (Universitat Politècnica de Catalunya, Spain):
Counting planar graphs and related families of graphs
Oliver Riordan (University of Oxford, UK):
Inhomogeneous Random Graphs
Gordon Royle (University of Western Australia):
Recent results on the chromatic and flow roots of graphs and binary matroids
Abstracts can be found by clicking on the talk titles above.
The speakers above will each give a 1 hour talk. These talks are intended to be accessible to postgraduate students, postdoctoral fellows, and researchers in all areas of combinatorics. In addition, participants are invited to give a talk of 20 minutes on any combinatorial topic. A problem session will be held on the last day.
Arrigo Bonisoli
(Università di Modena e Reggio Emilia, Italy)
Graph decompositions and symmetry
In this lecture I shall try to review some results which have been obtained in the area of factorizations and decompositions of complete graphs admitting an automorphism group with some specified properties. These properties primarily involve the action of the group on the objects of the decomposition, most often vertices, but also edges, subgraphs of the decomposition or factors of the factorization.
Classification theorems have been obtained in highly symmetric situations, for example when the group acts doubly transitively on vertices, and it is often the case that all examples arise from geometry in this context.
A ``less'' symmetric situation involves a group acting sharply transitively on vertices, which means for any two given vertices there exists precisely one group element mapping the first vertex to the second one. The vertices of the complete graph can be identified with group elements in this case, and the decomposition or factorization can be described entirely within the group by techniques which are generally known as ``difference'' or ``starter--like'' methods. Existence may be a non--tivial question and generally depends on the isomorhism type of the chosen group.
Peter J Cameron
(Queen Mary, University of London, UK)
Optimal block designs for combinatorialists
To a combinatorialist, a design is usually a 2-design or balanced incomplete-block design. However, 2-designs do not necessarily exist in all cases where a statistician might wish to use one to design an experiment. As a result, statisticians need to consider structures much more general than the combinatorialist's designs, and to decide which one is ``best'' in a given situation. This leads to the theory of optimal designs. There are several concepts of optimality, and no general consensus about which one to use in any particular situation.
For block designs with fixed block size k, all these optimality criteria are determined by a graph, the concurrence graph of the design, and more specifically, by the eigenvalues of the Laplacian matrix of the graph. It turns out that the optimality criteria most used by statisticians correspond to properties of this graph which are interesting in other contexts: D-optimality involves maximizing the number of spanning trees; A-optimality involves minimizing the sum of resistances between all pairs of terminals (when the graph is regarded as an electrical circuit, with each edge being a one-ohm resistor); and E-optimality involves maximizing the smallest eigenvalue of the Laplacian (the corresponding graphs are likely to have good expansion and random walk properties). If you are familiar with these properties, you may expect that related ``nice'' properties such as regularity and large girth (or even symmetry) may tend to hold; some of our examples may come as a surprise!
The aim of this talk is to point out that the optimal design point of view unifies various topics in graph theory and design theory, and suggests some interesting open problems to which combinatorialists of all kinds might turn their expertise. We describe in some detail both the statistical background and the mathematics of various topics such as Laplace eigenvalues of graphs.
Willem H Haemers
(Tilburg University, The Netherlands)
Structure and spectra of graphs
We present some recent results that involve regularity of graphs and their eigenvalues. The following questions are dealt with: when can one deduce from an appropriate spectrum of a graph G that (i) G is regular, (ii) G is distance-regular, (iii) G has a perfect matching?
Gholamreza B Khosrovshahi
(IPM, Iran)
Trades and t-designs
Trades, as combinatorial objects, possess interesting combinatorial and algebraic properties and play a considerable role in various areas of combinatorial designs. In this paper we focus on trades within the context of t-designs. A pedagogical review of the applications of trades in constructing halving t-designs is presented. We also consider (N,t)-partitionable sets as a generalization of trades. This generalized notion provides a powerful approach to the construction of large sets of t-designs. We review the main recursive constructions and theorems obtained by this approach. Finally, we discuss the linear algebraic representation of trades and present two applications.
Alexandr V Kostochka
(University of Illinois at Urbana-Champaign, USA)
Extremal graph packing problems: Ore-type versus Dirac-type
We discuss recent progress and unsolved problems concerning extremal graph packing, emphasizing connections between Dirac-type and Ore-type problems. Extra attention is paid to coloring, and especially equitable coloring, of graphs.
Daniela Kühn
(University of Birmingham, UK)
Embedding large graphs into dense graphs
What conditions ensure that a graph G contains some given spanning subgraph H? Since the corresponding decision problem is usually NP-complete, it makes sense to search for simple sufficient conditions. In my talk, I will focus on the case where H is a Hamilton cycle. A fundamental result of Dirac states that a minimum degree of |G|/2 guarantees a Hamilton cycle in an undirected graph G. This was generalized to directed graphs by Ghouila-Houri. Amongst others, I will discuss the following recent related results.
(i) The following analogue of Dirac's theorem for oriented graphs (an oriented graph is a digraph without 2-cycles): every sufficiently large oriented graph G with minimum out- and indegrees at least (3|G|-4)/8 contains a Hamilton cycle. This bound is best possible and answers a question of Thomassen from 1979 for large oriented graphs.
(ii) An approximate solution to a conjecture of Nash-Williams from 1975 concerning a digraph analogue of Chvatal's theorem (the latter gives a characterization of all those degree sequences which guarantee a Hamilton cycle in a graph).
(iii) Results on cycles of given length in oriented graphs of large minimum degree.
These results are joint work with Peter Keevash, Luke Kelly, Deryk Osthus and Andrew Treglown
Marc Noy
(Universitat Politècnica de Catalunya, Spain)
Counting planar graphs and related families of graphs
In this talk we survey recent results on the asymptotic enumeration of planar graphs and, more generally, graphs embeddable in a fixed surface and graphs defined in terms of excluded minors. We also discuss in detail properties of random planar graphs, such as the number of edges, the degree distribution or the size of the largest k-connected component. Most of the results we present use generating functions and analytic tools.
If time permits, we will also discuss the recent solution to the problem of counting graphs embeddable in a surface of fixed genus g.
Oliver Riordan
(University of Oxford, UK)
Inhomogeneous Random Graphs
Recently, Bollobás, Janson and Riordan introduced a very general family of random graph models, producing inhomogeneous random graphs with Q(n) edges. Roughly speaking, there is one model for each kernel, i.e. each symmetric measurable function from [0, 1]2 to the non-negative reals, although the details are much more complicated, to ensure the exact inclusion of many of the recent models for large-scale real-world networks.
A different connection between kernels and random graphs arises in the recent work of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi. They introduced several natural metrics on dense graphs (graphs with n vertices and Q(n2) edges), showed that these metrics are equivalent, and gave a description of the completion of the space of all graphs with respect to any of these metrics in terms of graphons, which are essentially bounded kernels. One of the most appealing aspects of this work is the message that sequences of inhomogeneous quasi-random graphs are in a sense completely general: any sequence of dense graphs contains such a subsequence. Alternatively, their results show that certain natural models of dense inhomogeneous random graphs (one for each graphon) cover the space of dense graphs: there is one model for each point of the completion, producing graphs that converge to this point.
Our aim here is to briefly survey these results, and then to investigate to what extent they can be generalized to graphs with o(n2) edges. Although many of the definitions extend in a simple way, the connections between the various metrics, and between the metrics and random graph models, turn out to be much more complicated than in the dense case. We shall prove many partial results, and state even more conjectures and open problems, whose resolution would greatly enhance the currently rather unsatisfactory theory of metrics on sparse graphs. This paper deals mainly with graphs with o(n2) but w(n) edges: a companion paper will discuss the (more problematic still) case of extremely sparse graphs, with O(n) edges.
Gordon Royle
(University of Western Australia)
Recent results on the chromatic and flow roots of graphs and binary
matroids
This paper surveys recent developments in the study of the real and complex roots of the chromatic and flow polynomials of graphs and matroids.