arXiv Code and data search.c 221000.dat plot5.ggb – Geogebra notebook geo5.sh – awk one-liner to format array to input parameters to Geogebra Errata Every time I wrote I should have written . This will be corrected in the final version. The pigeonhole upper bound is perhaps better written , since it arises as , where …
Author: babarber
Diffy naive
A week or so ago Rob Eastaway posted about the game Diffy on Twitter. Diffy begins with four numbers arranged around a cycle. Taking the (absolute values of) differences between adjacent pairs produces four more numbers around a cycle. If you start with positive integers then iterating this process eventually reaches . How many iterations …
Concentration inequalities
In early 2019 I gave three lectures on concentration inequalities from a combinatorial perspective to the postgraduate reading group SPACE (Sum-Product, Additive-Combinatorics Etc.) at the University of Bristol. I prepared some very rough notes on what was covered. You might also be interested in a scan of my undergraduate lecture notes on the same topic.
The Namer-Claimer game, part 2
Discrete Mathematics, Volume 344, Issue 3, March 2021, 112256 https://doi.org/10.1016/j.disc.2020.112256 arXiv I’ve previously written about the Namer-Claimer game. I can now prove that the length of the game is with optimal play from each side, matching the greedy lower bound. The upper bound makes use of randomness, but in a very controlled way. Analysing a truly …
Minimalist designs
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
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 …
Counting colourings with containers
On the maximum number of integer colourings with forbidden monochromatic sums, Hong Liu, Maryam Sharifzadeh and Katherine Staden Maryam spoke about this paper at this week’s combinatorics seminar. The problem is as follows. Let be the number of -colourings of a subset of with no monochromatic sum . What is the maximum of over all ? …
Linear programming duality
The conventional statement of linear programming duality is completely inscrutable. Prime: maximise subject to and . Dual: minimise subject to and . If either problem has a finite optimum then so does the other, and the optima agree. I do understand concrete examples. Suppose we want to pack the maximum number vertex-disjoint copies of a graph …