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 that shatters a -set has at least elements. How many -sets can we shatter with a family of size ? A block construction achieves . (Random is much worse.) Can in fact shatter constant fraction of all -sets. When , identify the ground set with , and colour by for .

Claim. A -set is shattered if and only if it is a basis for .

Proof. First suppose that is a basis. Then for any sequence , there is a unique vector such that . (We are just solving a system of full rank equations mod 2.)

Next suppose that are linearly dependent; that is, that they are contained in a subspace of . Choose orthogonal to . Then for any and any we have , so two of our colourings agree on .

We finish with the observation that random sets of vectors are fairly likely to span : the probability is

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

At the other end of the scale, we can ask how large a family is required to shatter every -set from . The best known lower bound is , and the best known upper bound is , 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 vertices into every tournament on vertices that implies that almost all oriented trees are unavoidable in this sense.

The Namer-Claimer game

Consider the following game played on the integers from to .  In each round Namer names a forbidden distance , then Claimer claims a subset of that does not contain any two integers at distance .  After finitely many rounds, Claimer will have claimed sets that cover the whole of , at which point the game ends.  How many rounds will there be with best play?

I’ve run this question out at a number of workshops and open problems sessions, and haven’t yet heard back about a success.  I’ll explain the known upper and lower bounds below the fold, but encourage you to spend a few minutes thinking about it before taking a look.

Nowhere zero 6-flows

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 on each edge are all less than .  Tutte conjectured that every bridgeless graph has a nowhere zero -flow (so the possible flow values are ).  This is supposed to be a generalisation of the -colour theorem.  Given a plane graph and a proper colouring of its faces by , push flows of value anticlockwise around each face of .  Adding the flows in the obvious way gives a flow on in which each edge has a total flow of in some direction.

Seymour proved that every bridgeless graph has a nowhere zero -flow.  Thomas Bloom and I worked this out at the blackboard, and I want to record the ideas here.  First, a folklore observation that a minimal counterexample must be cubic and -connected.  We will temporarily allow graphs to have loops and multiple edges.

We first show that is -edge-connected.  It is certainly -edge-connected, else there is a bridge.  (If is not even connected then look at a component.)  If it were only -edge-connected then the graph would look like this.

Contract the top cross edge.

If the new graph has a nowhere zero -flow then so will the old one, as the flow in the bottom cross edge tells us how much flow is passing between the left and right blobs at the identified vertices and so the flow the we must put on the edge we contracted.  So is -edge connected.

Next we show that is -regular.  A vertex of degree forces a bridge; a vertex of degree forces the incident edges to have equal flows, so the two edges can be regarded as one.  So suppose there is a vertex of degree at least .

We want to replace two edges and by a single edge to obtain a smaller graph that is no easier to find a flow for.  The problem is that in doing so we might produce a bridge.

The -edge-connected components of   are connected by single edges in a forest-like fashion.  If any of the leaves of this forest contains only one neighbour of then there is a -edge-cut, so each leaf contains at least two neighbours of .

If there is a component of the forest with two leaves then choose and to be neighbours of from different leaves of that component.

Otherwise the -edge-connected components of are disconnected from each other.  Now any such component must contain at least neighbours of , else there is a -edge-cut.  If some contains neighbours of then we can choose and to be any two of them.  Otherwise all such contain exactly neighbours of , in which case there must be at least two of them and we can choose and to be neighbours of in different components.

So is -regular and -edge-connected.  If is only -connected then there is no flow between -connected components, so one of the components is a smaller graph with no nowhere zero -flow.  If is only -connected then because is so small we can also find a -edge-cut.

Finally, we want to get rid of any loops and multiple edges we might have introduced.  But loops make literally no interesting contribution to flows and double edges all look like

and the total flow on the pair just has to agree with the edges on either side.

We’ll also need one piece of magic (see postscript).

Theorem. (Tutte) Given any integer flow of there is a -flow of that agrees with the original flow mod .  (By definition, flows of in one direction and in the other direction agree mod .)

So we only need to worry about keeping things non-zero mod .

The engine of Seymour’s proof is the following observation.

Claim. Suppose that where each is a cycle and the number of new edges when we add to is at most .  Then has a -flow which is non-zero outside .

Write for the set of edges added at the th stage.  We assign flows to in that order.  Assign a flow of in an arbitrary direction to ; now the edges in have non-zero flow and will never be touched again.  At the next stage, the edges in might already have some flow; but since there are only two possible values for these flows mod .  So there is some choice of flow we can put on to ensure that the flows on are non-zero.  Keep going to obtain the desired -flow, applying Tutte’s result as required to bring values back in range.

Finally, we claim that the we are considering have the above form with being a vertex disjoint union of cycles.  Then trivially has a -flow, and times this -flow plus the -flow constructed above is a nowhere-zero -flow on .

For , write for the largest subgraph of that can be obtained as above by adding cycles in turn, using at most two new edges at each stage.  Let be a maximal collection of vertex disjoint cycles in with connected, and let .  We claim that is empty.  If not, then the -connected blocks of are connected in a forest-like fashion; let be one of the leaves.

By -connectedness there are three vertex disjoint paths from to . At most one of these paths travels through ; let and be endpoints of two paths that do not.  These paths must in fact be single edges, as the only other way to get to would be to travel through .  Finally, since is -connected it contains a cycle through and , contradicting the choice of .

Postscript. It turns out that Tutte’s result is far from magical; in fact its proof is exactly what it should be.  Obtain a directed graph from by forgetting about the magnitude of flow in each edge (if an edge contains zero flow then delete it).  We claim that every edge is in a directed cycle.

Indeed, choose a directed edge .  Let be the set of vertices that can be reached by a directed path from and let be the set of vertices that can reach by following a directed path.  If  is not in any directed cycle then and are disjoint and there is no directed path from to .  But then there can be no flow in , contradicting the definition of .

So as long as there are edges with flow value at least , find a directed cycle containing one of those edges and push a flow of through it in the opposite direction.  The total flow in edges with flow at least strictly decreases, so we eventually obtain a -flow.