The 2023 Dutch Days of Combinatorics take place in-person centrally in Utrecht on 6 & 7 March at Museum Speelklok. We invite all to submit a contributed talk (~20 min) and/or lightning talk (~5 min).
The schedule and talk abstract can be found below.
The purpose of the DDoC is to meet up, share ideas, and build/strengthen bonds within the combinatorial community in the Netherlands. We are excited to showcase some of the depth and breadth of Dutch combinatorics through talks by the following speakers:
Suppose a group of mathematicians need to decide between two different coffee machines for the department.
Option A
Option B
We ask them to raise their hand if they prefer option A, and record the subset of that raised their hand. For each such subset, we specify whether option A wins or loses. This gives a collection of winning coalitions. Their are a few very natural assumptions for a ‘fair’ way of deciding who won:
If more people vote for option A, then option A is more likely to win. In combinatorics terms, is an upset.
Option A and B have an equal probability of winning. That is, .
So far what we have defined is equivalent to a maximal intersecting family. We will add one more assumption which is modelled in a way which is perhaps a bit less natural. The automorphism group Aut() of our set system is the set of bijections for which for all . We call symmetric if the action of its automorphism group is transitive, that is, for all , there exists a Aut() with .
All voters are treated equally. Our set system is symmetric.
Such a fair game or symmetric maximal intersecting family need not exist. It is easy to find one for odd: indeed, we can use the voting rule most often used in practice called the majority rule, for which . However, the existence for even is far from understood. Isbell proved the following result in his first Homogenous Games paper.
Lemma (Isbell) Let . The following statements are equivalent.
There exists a maximal intersecting family on that is symmetric.
There exists a transitive subgroup of for which every has at least one odd cycle.
There exists a transitive subgroup of for which every 2-power-order element has a fixed point (that is, ).
Isbell conjectured in 1960 that there is a finite bound for each odd such that no symmetric maximal intersecting family exists for for all . Peter Cameron was interested in this problem, and introduced cyclically covering subspaces (the topic of our paper, defined further below). He noticed that a small cyclically covering subspace in (say codimension ), can be used to construct a large symmetric maximal intersecting family (say for ). (This connection that is explained in detail by Cameron, Ellis and Raynaud.)
Let denote the cyclic shift, e.g. and .
Definition A cyclically covering subpace is a linear subspace with the property that for all , there exists a shift for which .
It is easy to construct such a subspace: we can always take . It is also clear the subspace cannot be too small, e.g. the all ones and all zeros vectors always need to be a part of . How small can such a cyclically covering subspace be (given )? Define as the largest codimension ( minus dimension) of a cyclically covering subspace in . More than 25 years ago, Peter Cameron posed the question whether as over the odd integers (see Problem 190, and his blog that we are proud to be mentioned on). The main result of our paper answers this question negatively (conditional on Artin’s conjecture).
Theorem (Aaronson, G., Johnston) If is a prime for which the polynomial is irreducible over , then .
There are infinitely many such primes if Artin’s conjecture is true. Artin conjectured in 1927 a precise density for such primes among the primes, which seems about correct for the primes below 300.000, as can be seen below.
The first couple of Artin primes have their own OEIS sequence.
The proof of our result is quite long. Some of the main steps we take are:
We reformulate the problem by switching to the orthogonal complement: it suffices to prove that there are no linearly independent such that the orthogonal complement of these is cyclically covering.
We show we may assume that . This is the only step where we use our assumption that is irreducible, through the fact that splits into the sum of two fields . Letting a vector correspond to the polynomial , shifting corresponds to multiplying by . This reformulation was introduced by by Cameron, Ellis and Raynaud, who use algebraic arguments to prove several bounds on .
We say a vector is symmetric if and . E.g. is symmetric and is not. We show, for any prime , that cannot ‘work together’ with two additional vector if either is symmetric.
We then try to show our conjecture that there is no non-symmetric vector such that the orthogonal complement of is a cyclically covering subspace of codimension 2. For this we reformulate into Cayley graphs, giving the equivalent statement of our conjecture below.
For primes , by studying additive properties of the set of for which , we try to reduce our conjecture to the case in which is contained in a small arithmetic progression (which we can handle). We are able to do this whenever the Cayley graph we constructed has no directed cycles of length 4 or 6. Whenever this is not the case, we fail to prove our conjecture, but with some additional case analysis work we show there can’t be an additional , which suffices for our theorem.
Conjecture Let be an odd integer which is not divisible by 7 and let be a Cayley digraph on vertex set . Then has no odd-sized induced subgraph with all outdegrees odd if and only if is a graph.
A Cayley digraph on vertex set is a directed graph where a fixed subset of specifies the arcs: if and only if . This is a graph if and only if is symmetric, that is, (no self-loops) and (all edges are bidirectional).
The Cayley graph with generating set for . The graph induced on is of odd size and every vertex has odd outdegree. This implies that the vector has no shift within the orthogonal complement of and .
One of the directions of our conjecture follows from the handshake lemma. We checked the other direction for all by computer search.
Cameron, Ellis and Raynaud also introduced the generalisation of to for arbitrary prime powers . Their problem of determining for which values of we have remains open. Several other interesting open problems can be found in our paper.
Suppose you are on a grid , starting in the origin. At each iteration, you select a direction uniformly at random from the set {North, South, East, West}, after which you set one step in that direction. It is a well-known result that such a walk will visit each point infinitely often in and , but not in higher dimensions (see e.g. Section 5.9 of Part A Probability in Oxford). It turns out that this is even the case if you restrict this simple symmetric random walk to a connected subgraph of the grid, where you `skip’ an instruction if there is no edge present to walk on.
Hence for each subgraph of the grid, a simple symmetric random walk returns to the origin infinitely often with probability one (since there is always a positive probability you walk from one place to another, it suffices to return infinitely often to 0). What if we switch around the `for each’ and the `with probability one’ in this sentence? As the countable union of null events is again a null event, for any countable (in particular finite) collection of subgraphs we know that our random walk returns to 0 infinitely often on all those graphs with probability one. However, the collection of all subgraphs is not countable, and it turns out that with probability one there actually is an exceptional graph on which our random walk is not `recurrent’. The following nice result was obtained by Aru and Narayanan (see https://arxiv.org/abs/1805.06277v1) and independently Balister, Bollobás, Leader and Walters.
Theorem If is a simple random walk on , then
.
A slice of the graph between two consecutive vertical lines; the graph has vertical lines present at all -coordinates of the form .
More information on the construction of .
A technical note first: we have a random variable that gives us a sequence of instructions for each . We need to show that on a subset of of measure 1, we can construct a graph for which the corresponding walk does not return to 0 infinitely often.
The general idea is the following: we read our random instructions and reveal the graph as we go. Suppose we try to let our random walk “drift” to the East direction. Whenever we have not revealed edges yet, we allow the walk to continue on eastward if it wants to do so, but never reveal any “westward” edges. It turns out one needs to be a bit more clever than this: instead, consider a graph which has all vertical lines present at all -coordinates of the form , where the segments in between will be revealed by the rules above. All line segments have only a single horizontal line connecting them (and possibly many lines starting from the left, not quite reaching the right); the idea will be to ensure that the probability that you get from one vertical line to the next, is much larger than the probability that you walk back to the previous line (which can only happen at a unique y-value). Let be the event we walk back to before we reach for the first time (after having reached ). If , then by Borel-Cantelli only finitely many happen with probability one, and in particular the walk returns to 0 finitely often.
Juhan Aru and Bhargav Narayanan moreover showed that even if you have a finite collection of independent random walks, there still almost surely exists a graph on which none of them are recurrent. In our joint paper, we provide some answers to the question of what the largest cardinality of such a collection could be. We show that for any countable collection of independent simple random walks, there is, with probability one, a subgraph on which none of these random walks is recurrent. When modelling uncountably infinite collections, it is a bit less clear what the appropriate phrasing of the question is.
One natural formulation is in the language of branching random walks. A branching random walk on starts with a single particle at the origin. At each time step, each particle independently generates a number of additional particles at its current location according to some fixed offspring distribution, and we say that this offspring distribution is nontrivial if the number of offspring is nonzero with positive probability. Independently of the other particles and their history, all particles then take a step in a direction chosen uniformly at random, which leads to a random family of dependent simple random walks. It turns out that in this case, with probability 1, for each graph there is some branch of the walk that is recurrent.
Theorem. Fix and let be a family of random walks generated by a branching random walk on with a nontrivial offspring distribution. Then
The proof uses a rapidly-increasing sequence of times . At each time , and for every possible finite subgraph contained in the box , we choose a representative particle . We then show that, with very high probability, for each such representative particle and every possible extension of the corresponding graph onto , some descendant of visits every vertex of with distance at most (in ) to the origin, and ends up exactly at or one step away from the origin at time .
One of the original motivations for considering the problem of the random walk on the grid comes from a very nice question from Spink on universal traversal sequences.
Problem Does there exist a fixed set of directions, such that the walk which follows the corresponding instructions is recurrent on every subgraph of the grid?
A popular way of constructing such a universal transversal sequence is by choosing the sequence at random; however apparently their exist exceptional graphs for such a random sequence.
For some classes of subgraphs of the grid such a sequence can be constructed, but the general problem is still open.
Update Due to covid, the workshop ended up taking place July 18-22, 2022. For more information, see our our website.
The Young Researchers in Combinatorics workshop is aimed at PhD students and early-career academics working in Extremal and Probabilistic Combinatorics and related fields. By building an environment of mostly young researchers, we hope the participants will feel free to contribute their ideas openly, thus preparing them to undertake their own research projects.
We aim to host around 10 invited participants and about 25 PhD students for a week between 19 and 25 July 2020 at ICMS Edinburgh. Accommodation and refreshments are provided for all participants, as well as a conference dinner. A registration fee of 100GBP is payable by all non-invited participants. The confirmed invited participants are:
The workshop consists mostly of working sessions in which participants collaborate on research problems, and a limited number of talks and lectures. All participants have the chance to contribute a subset of the following items to the workshop: – research problem with suggested reading; – lecture on a useful method; – short talk about their own research.
What intersection sizes are possible between a hypercube and a linear subspace? We continue the work of Melo and Winter related to this question.
A 2-dimensional linear subspace can have 1, 2, 3 or 4 points in common with a (hyper)cube.
Let denote the set of possible intersection sizes that a -dimensional linear subspace can have with the -dimensional hypercube (in Euclidean space). As the 0-vector will always be present in , this will be an integer of size at least 1. Moreover, an upper bound of is immediate from the following reformulation:
.
(Proof of reformulation).
To see this equivalence, note that we can parametrise any -dimensional linear subspace as for some linear map .
(Proof of reparametrisation).
Let be an integer. We first show there is an injective linear map from to a -dimensional space. As , there must be some basisvector which is not contained in . In that case, the map
is injective on . Indeed, if would satisfy for all , then . Suppose wlog that . Properties of a linear subspace now imply that , giving a contradiction.
After renumbering coordinates, we may now assume that the map
is an injective linear map, and the image will be a -dimensional linear subspace, hence is a linear bijection; the inverse is the linear map we are looking for.
This implies that
.
Note that the linear map is determined by the values it takes on the basis vectors of . The reformulation makes it easy to show that
whenever and .
Let be a map from . We claim that there is a with . To handle , define to be a very large negative value for ; in that case, is only possible if for (in which case ). Set to extend a map to to a map to .
For , all intersection sizes are possible already when (see the figure above). Is for large?
Melo and Winter showed that for a -dimensional subspace, for large all intersection sizes for are possible, whereas an intersection between and can never be achieved. They conjectured that no values in the other gaps can be achieved either. Our first result shows this is almost true. Let .
Theorem For , and ,
.
In fact, we determine exactly for all . There is one additional value , which appears already for .
Melo and Winter also conjectured that all intersections below can be achieved; we show this is false by proving that slightly below in fact most values cannot be achieved.
Theorem For and any ,
Our proofs work by first solving the case and then considering as the intersection of various cases. Indeed, we can consider the maps for and then it is not difficult to see that
, where
writing for the points in whose image under lies in . We use the following auxiliary results:
As noted by Melo and Winter, if .
We prove the contrapositive. Suppose . For any , if , then . Hence either or is not in , thus .
We may still assume this if as long as .
In fact, the value can be achieved in various ways by setting equal to (for small ).
We prove that a non-trivial intersection with an additional gives a significant reduction of . The reduction is particularly strong if , hence if wlog is the part taking a value outside of , then by above and it turns out that any strictly smaller lands out of our range.
(and hence ) is too small unless for all but at most 9 of the .
Suppose and
, , .
Then we prove that
(Proof idea)
The smallest value can take is , which is achieved by setting exactly for . If is changed to for an element , then the value of will increase by 1. In order to get to , such changes have to be made which can be done in exactly ways. The coordinates mapping to (the for ) have no effect on the value of so each can individually be included or not; this gives the factor .
This implies that
The largest binomial coefficient grows as , and calculation confirms that for any we find that .
If multiple intersect and none of them is redundant, then the sets of values for which must form a particular “shape”.
We show this by generating all cases using computer search, which is computationally feasible using the claims proved above.
We define the shape of a map to be a hypergraph which has as vertices and the sets as edges. We call a map minimal if each has a value in for which it is the only one covering it, and the `constraint is not redundant’, i.e. where . The minimal shapes for which is in our range of interest, tend to take a particular form: a (3,2)-star or a (2,1)-star.
A (3,2)-star with two edges.
It turns out that for example the following statement holds.
Suppose is a minimal linear map with for all , for which . Then either the sets form a (2,1)-star or a (3,2)-star, or .
It remains open which intersection sizes are possible below , and in particular if all values would have been present with a smaller upper bound. We pose the following conjecture.
Conjecture For every constant , for sufficiently large, a positive fraction of the values in cannot be achieved as an intersection between a -dimensional subspace and a hypercube.
The 26th Postgraduate Combinatorial Conference (PCC) will be held in Oxford on 10th-12th June 2019.
The PCC is an established conference organised by, and for, current research students in all areas of combinatorial and discrete mathematics, under the auspices of the British Combinatorial Committee. The PCC is mainly aimed at UK-based students, but is also open to those from abroad.
The aim of the conference is to allow research students to discuss their research in a relaxed environment, to gain practice at presenting their research outside of their own department, and to meet other young researchers in their area. Each student is encouraged to contribute by giving a talk which will last 25 minutes (including 5 minutes question and answer time).
The fee includes the conference reception, the conference dinner and refreshments during the breaks. We also have limited funds to cover travel expenses, hopefully up to the value of around £50-60 per person.
We gratefully acknowledge support from the LMS and the BCC.
[This blog post is based on a joint paper with Hannah Guggiari and Alex Scott]
A graph consists of a set of vertices and a set of edges which may connect two (distinct) vertices. (There are no self-loops or multiple edges.)
A very basic question about graphs is: Is a graph determined by its induced subgraphs? For a graph and a vertex , a card of the graph is an induced subgraph obtained by removing the vertex and all adjacent edges. The deck of the graph is the collection of cards , allowing multiples. An example of a deck of card is given below.
Below the cards, we see how the cards can be obtained by removing vertices from a single graph, removing one at a time and removing each vertex exactly once.
Can two non-isomorphic graphs have the same deck of cards? Yes, if the graphs have two vertices.
If we see a single vertex twice, then we know the original graph had two vertices but there is no way for us to know whether there is an edge between them.
More than 60 years ago, Kelly and Ulam made the beautiful conjecture that if two graphs on at least three vertices have the same deck, they must be isomorphic. In 1977, Bondy and Hemminger wrote the following about this conjecture:
The Reconstruction Conjecture is generally regarded as one of the foremost unsolved problems in graph theory. Indeed, Harary (1969) has even classified it as a “graphical disease” because of its contagious nature. According to reliable sources, it was discovered in Wisconsin in 1941 by Kelly and Ulam, and claimed its first victim (P. J. Kelly) in 1942. There are now more than sixty recorded cases, and relapses occur frequently (this article being a case in point).
There are many subtleties in the problem which might not be apparent at first sight; for example, if two vertices and have the same card (i.e. ) then they are not necessarily “similar” in the graph, that is, there does not necessarily exist a graph automorphism mapping to .
Rather than reconstructing the entire graph, can we at least read off some information about the graph? If a graph has vertices then
since each edge appears in all cards except for the two corresponding to vertices it is adjacent to. So we can read off the number of edges of the graph (the size) if we are given a full deck of cards. What if we have only access to a subset of the cards? In Size reconstructibility of graphs Alex Scott, Hannah Guggiari and I describe a way to reconstruct the size of the graph if at most cards are missing from the deck (for large). The best previous result in this direction was the case in which two cards are missing.
Our proof works as follows:
We first note that if we have been given the cards , we can still compute , which allows us to obtain an (over)estimate on the number of edges.
The degree of a vertex is the number of edges adjacent to it. Note that on the card , exactly the edges adjacent to are missing. Hence . We will try to approximate the degree sequence , where gives the number of vertices of degree , in two different ways.
Firstly, using our estimate on the number of edges, we can still approximate the degree of the vertices of the cards that have been given: Since we overestimate the number of edges, we also overestimate for every vertex, but always by the same amount This means our approximated degree sequence is the actual degree sequence but shifted to the right, and moreover some values have been underestimated (since some of the cards are missing). If we could recover the shift we could find since we know
Secondly, we discover many small values exactly. Let denote the number of vertices of degree in . We discover many values of from our magic formula
.
We almost know the quantity on the left-hand side. If we knew say exactly, then we can find exactly if we find an estimate whose error is guaranteed to be , as we know that is an integer (we then round this error away). For a similar reason, we are able to “guess” and if both of these are small, and is “not too near a bad fraction”. Hence we can discover some of the values, and can then use this knowledge to find some of the nearby values as well. In fact, we can either find the adjacent value or discover it is ‘large’.
We either reconstruct the entire degree sequence (then we can read off the number of edges from this) or discover some large values. Suppose that we find a segment as in the picture below: one large value, and to one side of it a bunch of known values, many of which are small.
We “match up” the known values to various shifts of For the correct shift, the error will be small, whereas for any other shift the error is lower bounded by the difference between large and small in the figure below. This allows us to recover and then the number of edges.
Some interesting open problems include:
The original graph reconstruction conjecture, for which the edge variant is also unknown. (The directed graph, infinite graph and hypergraph analogues are false.) This is also unknown for “nice” graph classes such as bipartite graphs or planar graphs.
Improving our result beyond or extending it to recovering different information about the graph, such as the degree sequence or the number of triangles.
[This blog post is based on a joint paper with Karolina Okrasa, Pawel Rzążewski, Alex Scott, Paul Seymour and Sophie Spirkl. A short talk is available on video.]
The decision problem 3-COLOURABILITY asks whether the vertices of a given graph can be coloured with three colours in such a way that vertices which are connected by an edge receive different colours. This problem is well-known to be NP-hard, meaning it is difficult to solve in general in some sense. What happens if we restrict the class of graphs? Is it due to a particular structure in the graph that graphs are easier or harder to colour?
This graph can be coloured with 3 colours: the nodes with the same colour are not connected. Such colourings can model various real-life scenario’s, e.g. the colours could represent time-periods and two tasks could have an edge between them if they cannot happen simultaneously. A 3-colouring is then a conflict-free assignment of the tasks to time periods such that at most three periods are required.
A graph is called -free if it does not contain the graph as induced subgraph (meaning that one can remove vertices, but not edges, e.g. a complete graph has only complete graphs as induced subgraphs). It turns out that -colouring is still NP-hard if you restrict to the class of graphs not containing a cycle or the claw graph (for all ). If we assume is connected, then the remaining cases are paths on vertices.
After a series of paper, the complexity status of -COLOURABILITY of -free graphs has been determined, except for and . The open question is hence: does colouring become easier if restricted to graphs which do not contain long induced paths? Intuitively, long paths may allow for “long-term interactions”. In H-colouring Pt-free graphs in subexponential time, my co-authors and I show that in some sense this case is easier: there is a subexponential-time algorithm for deciding 3-colourability. Even more, the number of 3-colourings can be counted in subexponential time. Under the Exponential Time Hypothesis (which says that 3-SAT cannot be solved in subexponential time), such an algorithm cannot exist for the other graphs than nor for (for, say, ).
Another nice open problem about the complexity of 3-COLOURABILITY, is its complexity on diameter 2 graphs. Several subexponential-time algorithms are known (Mertzios and Spirakis, Dębski, Piecyk, Rzążewski) but it is not known whether 3-COLOURABILITY can be solved in (quasi-)polynomial time on diameter 2 graphs. The problem 4-COLOURABILITY is easily seen to be NP-hard even when restricted to diameter 2 graphs: indeed, one can add a universal vertex to decrease the diameter to any graph to 2, and the resulting graph is 4-colourable if and only if the original was 3-colourable.
In the -free case, it also not so strange that 4-COLOURABILITY is more difficult. Indeed, when four colours are available, one can create two types of vertices, say type I and type II. If all type I vertices are adjacent to all type II vertices, than any induced path can only contain a bounded number of type I and type II vertices. At the same time, colourings still have a lot of flexibility when two colours are allocated to one type and two colours to the other type. When considering 3-COLOURABILITY, these kinds of tricks are not possible in a potential NP-hardness reduction, and the most ‘gadget’ approaches would automatically results in long induced paths alternating between variable and clause gadgets.