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.

Shagnik Das

Andrew McDowell

Tássio Naia

Leave a Reply Cancel reply