One-Day Meeting in Combinatorics

12 June 2023, 1.00 PM - 12 June 2023, 5.30 PM

LG.02, School of Mathematics, Fry Building, Woodland Road, Bristol, BS8 1UG

This One-Day Meeting in Combinatorics, taking place in LG.02 the afternoon of Monday 12^th June (1pm-5:30pm) in the University of Bristol's Fry Building, features talks from four internationally-renowned researchers.

There is no registration fee, and refreshments will be provided during the afternoon coffee break. Please register using the link below if you would like to attend, for catering and room-booking purposes. After the meeting, at around 5:30 pm, some of us will head to a nearby pub; all delegates are invited to join.

Speakers:

Paul Balister (Oxford)

Title: Counting graphic sequences via integrated random walks

Abstract: Given an integer n, let G(n) be the number of integer sequences n−1 >= d_1 >= d_2 >= ... >= d_n >= 0 that are the degree sequence of some graph. We show that G(n)=(c+o(1))4^n/n^{3/4} for some constant c>0, improving both the previously best upper and lower bounds by a factor of n^{1/4+o(1)}. The proof relies on a translation of the problem into one concerning integrated random walks.

Joint work with Serte Donderwinkel, Carla Groenland, Tom Johnston and Alex Scott.

Julia Boettcher (LSE)

Title: The chromatic profile of a graph

Abstract: Determining the chromatic number of a graph is a difficult but important problem. Hence, it is not surprising that a variety of questions in Graph Theory concern the search for meaningful upper bounds for the chromatic number of certain families of graphs. One type of graph family that received considerable attention is that of H-free graphs, that is, the family of graphs G which do not contain a given graph H as a subgraph. By an old result of Erdős the chromatic number of H-free graphs G can be arbitrarily large (when H is not a forest). Erdős and Simonovits then asked what happens if we additionally introduce a minimum degree for G. This initiated the study of the so-called chromatic profile of a graph H, opening up a number of important directions of research where much remains open today.

Sean Eberhard (QUB)

Title: Group theory without groups

Abstract: The theory of primitive coherent configurations (PCC's), which are loosely speaking "multicoloured strongly regular graphs", has sometimes been described as "group theory without groups" because of its close connection to classical permutation group theory despite its purely combinatorial formulation. One of the theory's great successes was a beautiful 1981 result of Babai that a nontrivial PCC of degree n has at most exp O(4n^(1/2) log^2 n) automorphisms. This implies the same bound for the order of a non-2-transitive primitive permutation group of degree n. Babai also conjectured that PCC's with more than exp(n^epsilon) automorphisms are of a specific form called Cameron schemes. In this talk we will give an introduction to this general theory, an overview of Babai's proof, and the description of a new class of examples contradicting Babai's conjecture. This new class of examples ("Hamming sandwiches") turns out to be quite rich and includes a large number of examples based on combinatorial designs.

Alex Scott (Oxford)

Title: On a problem of El-Zahar and Erdos

Abstract: Two subgraphs A,B of a graph G are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erdos in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results.

We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number. Second, we look at what happens if we replace the hypothesis that G has large chromatic number with the hypothesis that G has sufficently large minimum degree. This, together with excluding K_t, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding a complete graph we exclude a complete bipartite graph. Finally, we discuss analogous problems for tournaments.

This is joint work with Tung Nguyen and Paul Seymour.

Programme:

1.00pm - 2.00pm Alex Scott (Oxford): On a problem of El-Zahar and Erdos.

2.00pm - 3.00pm Julia Boettcher (LSE): The chromatic profile of a graph.

3.00pm - 3:30pm Coffee break.

3:30pm - 4:30pm Sean Eberhard (QUB): Group theory without groups.

4:30pm - 5:30pm Paul Balister (Oxford): Counting graphic sequences via integrated random walks.

5:30pm - 8:00pm (or later) Pub.

8:15pm onwards: Dinner (for speakers and organisers only).

All talks will take place in LG.02, Fry Building.

Registration

Please register via the following link. The deadline for registration is Thursday 8 June, 5pm.

Funding

We have some funds to support the travel of UK-based PhD students to and from the meeting; if you are a UK-based PhD student and would like to apply for this, please email david.ellis@bristol.ac.uk, enclosing a short statement of support from your PhD supervisor (note that one or two lines suffice for the latter).

Contact information

For practical information please contact maths-conference-administrator@bristol.ac.uk