Tag: graphs

Minimalist designs

Published by babarber on

Ben Barber, Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, Deryk Osthus Random Struct Alg. 2020; 57: 47– 63. https://doi.org/10.1002/rsa.20915 In Edge decompositions of graphs with high minimum degree, Daniela Kühn, Allan Lo, Deryk Osthus and I proved that the edge sets of sufficiently dense graphs satisfying necessary divisibility conditions could be partitioned into copies of …

Chromatic number of the plane

Published by babarber on

The unit distance graph on has edges between those pairs of points at Euclidean distance .  The chromatic number of this graph lies between (by exhibiting a small subgraph on vertices with chromatic number ) and (by an explicit colouring based on a hexagonal tiling of the plane).  Aubrey de Grey has just posted a …

Random Structures and Algorithms 2017

Published by babarber on

A partial, chronologically ordered, list of talks I attended at RSA in Gniezno, Poland. Under construction until the set of things I can remember equals the set of things I’ve written about. Shagnik Das A family of subsets of that shatters a -set has at least elements. How many -sets can we shatter with a …

Matchings without Hall’s theorem

Published by babarber on

In practice matchings are found not by following the proof of Hall’s theorem but by starting with some matching and improving it by finding augmenting paths.  Given a matching in a bipartite graph on vertex classes and , an augmenting path is a path from to such that ever other edge of is an edge of …

Matchings and minimum degree

Published by babarber on

A Tale of Two Halls (Philip) Hall’s theorem.  Let be a bipartite graph on vertex classes , .  Suppose that,  for every , .  Then there is a matching from to . This is traditionally called Hall’s marriage theorem.  The picture is that the people in are all prepared to marry some subset of the …

Partition regularity and other combinatorial problems

Published by babarber on

This is the imaginative title of my PhD thesis.  It contains four unrelated pieces of work.  (I was warned off using this phrasing in the thesis itself, where the chapters are instead described as “self-contained”.) The first and most substantial concerns partition regularity.  It is a coherent presentation of all of the material from Partition …

Nowhere zero 6-flows

Published by babarber on

A flow on a graph is an assignment to each edge of of a direction and a non-negative integer (the flow in that edge) such that the flows into and out of each vertex agree.  A flow is nowhere zero if every edge is carrying a positive flow and (confusingly) it is a -flow if the flows …