Random Structures and Algorithms 2017

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 [n] that shatters a k-set has at least 2^k elements. How many k-sets can we shatter with a family of size 2^k? A block construction achieves (n/k)^k \approx e^{-k} \binom n k. (Random is much worse.) Can in fact shatter constant fraction of all k-sets. When n = 2^k-1, identify the ground set with \mathbb F_2^k \setminus \{0\}, and colour by \chi_w(v) = v \cdot w for w \in \mathbb F_2^k.

Claim. A k-set is shattered if and only if it is a basis for \mathbb F_2^k.

Proof. First suppose that v_1, \ldots, v_k is a basis. Then for any sequence \epsilon_i, there is a unique vector w such that v_i \cdot w = \epsilon_i. (We are just solving a system of full rank equations mod 2.)

Next suppose that v_1, \ldots, v_k are linearly dependent; that is, that they are contained in a subspace U of \mathbb F_2^k. Choose w orthogonal to U. Then for any u \in U and any w' we have u \cdot w' = u \cdot (w+w'), so two of our colourings agree on v_1, \ldots, v_k. \Box

We finish with the observation that random sets of k vectors are fairly likely to span \mathbb F_2^k: the probability is

    \[ 1 \cdot (1 - 1/2^k) \cdot (1 - 1/2^{k-1}_ \cdot \cdots \cdot (1-1/2) \geq 1 - \sum_j=1^k 1/2^j > 0. \]

Blowing up this colouring gives a construction that works for larger n.

At the other end of the scale, we can ask how large a family is required to shatter every k-set from [n]. The best known lower bound is \Omega(2^k \log n), and the best known upper bound is O(k2^k \log n), which comes from a random construction. Closing the gap between these bounds, or derandomising the upper bound, would both be of significant interest.

Andrew McDowell

At the start of his talk in Birmingham earlier this summer, Peter Hegarty played two clips from Terminator in which a creature first dissolved into liquid and dispersed, then later reassembled, stating that it had prompted him to wonder how independent agents can meet up without any communication. Andrew tackled the other half of this question: how can non-communicating agents spread out to occupy distinct vertices of a graph? He was able to analyse some strategies using Markov chains in a clever way.

Tássio Naia

A sufficient condition for embedding an oriented tree on n vertices into every tournament on n vertices that implies that almost all oriented trees are unavoidable in this sense.

Partition regularity and other combinatorial problems

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 regularity in the rationals, Partition regularity with congruence conditions and Partition regularity of a system of De and Hindman.

The remaining three chapters are expanded versions of Maximum hitting for


sufficiently large, Random walks on quasirandom graphs and A note on balanced independent sets in the cube.1

1 “A note … ” was fairly described by one of my examiners as a “potboiler”.  It was also my first submitted paper, and completed in my second of three years.  Perhaps this will reassure anybody in the first year of a PhD who is worrying that they have yet to publish.

Maximum hitting for n sufficiently large

Barber, B. Graphs and Combinatorics (2014) 30: 267. PDF

Borg asked what happens to the Erdős-Ko-Rado theorem if we only count sets meeting some fixed set X, and answered the question for |X| \geq r, the size of the sets in the set family. This paper answers the question for |X| < r, provided n, the size of the ground set, is sufficiently large.

There is a typo in the proof of Theorem 4 in the journal version. The line beginning “By Lemma 9, \mathcal F(2, n, G)(X) has size polynomial in n …” should read “By Lemma 9, \mathcal F( r, n, G)( X) …”. Thanks to Candida Bowtell for spotting this.