School of Mathematics, University of Bristol, UK

Supported by the Heilbronn Institute Small Grants Scheme

The Bristol One-Day Meeting in Combinatorics is an annual conference in Bristol with talks on a wide variety of topics within Combinatorics. Talks will cover recent developments in extremal and probabilistic combinatorics, additive combinatorics, structural graph theory and rigidity theory. The conference aims to be accessible to all and is free to attend.

Organisers:

Jonathan Chapman (Bristol)
Sean Dewar (Bristol)
David Ellis (Bristol)
Tom Johnston (Bristol)
Jonathan Passant (Bristol)

Invited Speakers:

Marina Iliopoulou (Athens).

Title: On integer distance sets.

Abstract: An integer distance set is a set in the Euclidean plane with the property that all pairwise distances between its points are integers. In this talk we will show that any integer distance set contains all but very few of its points on a single line or circle. This helps us address some questions of Erdős. In particular, we deduce that integer distance sets in general position (no 3 points on a line, no 4 points on a circle) are very sparse, and we derive a near-optimal lower bound on the diameter of any non-collinear integer distance set of a given size. Our proof uses existing refinements of the Bombieri-Pila determinant method. This is joint work with Rachel Greenfeld and Sarah Peluse.

Bill Jackson (QMUL).

Title: Rigidity of simplicial manifolds.

Abstract: A d-dimensional framework is a pair (G,p) where G=(V,E) is a graph, and p: V \to R^d. The length of each edge of (G,p) is the Euclidean distance between its endpoints. The framework is said to be rigid if every continuous motion of the vertices of (G,p) which preserves the  edge lengths, preserves the  distances between all pairs of vertices. It is said to be globally rigid if every realisation of G in R^d which has the same edge lengths as (G,p), has the  same distances between all pairs of vertices. A graph G is said to be rigid (respectively, globally rigid), in R^d, if every (or equivalently, some) generic realisation of G in R^d is rigid (respectively, globally rigid). Both properties have been characterised for graphs when d=1,2. Extending these characterizations to  R^d for d at least 3 is an important open problem in discrete geometry.

Simplicial manifolds provide a large family of graphs for which we can determine both rigidity and global rigidity in R^d. Indeed, the first theorem on the rigidity of frameworks is a celebrated result of Cauchy which implies that the 1-skeleton of every convex simplicial polyhedron is rigid in R^3. This result was extended to convex d-polytopes in R^d for all d at least 3, by Whiteley. Kalai used Whiteley's theorem to deduce that 1-skeleta of simplicial d-manifolds are generically rigid in R^{d+1} when d is at least 3. Fogelsanger introduced an ingenious new proof technique in his PhD thesis in 1988 to show that the same result holds for all d at least 2.

I will describe recent joint work with  James Cruickshank and Shin-ichi Tanigawa in which we obtain analogous results for global rigidity, symmetric manifolds and rigidity when we fix the volume of faces of dimension greater than one. 

Robert Johnson (QMUL).

Title: Correlation and Intersection: from Sets to Permutations via Orders

Abstract: We will discuss two extremal topics on permutations. The first is analogues of the Harris-Kleitman inequality for families of permutations. It turns out that there are two natural notions of what it means for a family of permutations to be an up-set (corresponding to the strong and weak Bruhat orders) and surprisingly the correlation that occurs in the two cases is quite different. The second is a new notion of intersection for permutations. Through these two examples, we will see a framework for translating extremal set theory concepts into the realm of permutations which has the potential to yield many open questions. This is based on joint work with Imre Leader and Eoin Long.

Orit Raz (HUJI).

Title: Sharp threshold for rigidity of random graphs

Abstract: For d at least 1, it is an easy fact that a graph G must have minimum degree at least d in order to be rigid in R^d. In the talk I will present a recent work, joint with A. Lew, E. Nevo and Y. Peled, where we show that the threshold probability for G(n, p) to be d-rigid coincides with the known threshold for having minimum degree d.

Register here.

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