Carla Groenland - Extremal and Probabilistic Combinatorics

Extremal and probabilistic combinatorics

The word 'extremal' indicates that the type of question is about maximising or minimising something, subject to certain constraints. For example, how many edges can an n-vertex graph have without creating a triangle? Such questions can also be asked for other discrete structures than graphs, such as partially ordered sets or permutations.

The word 'probabilistic combinatorics' I have taken rather broadly below: studying discrete random objects or using randomness to prove results about discrete objects.

Poset saturation

The following two papers are about poset saturation in the Boolean lattice (hypercube with inclusion as partial order).

Paul Bastide, Carla Groenland, Maria-Romina Ivan and Tom Johnston, A Polynomial Upper Bound for Poset Saturation, arXiv:2310.04634, accepted by European Journal of Combinatorics.
We provide a polynomial upper bound using VC dimension.
Paul Bastide, Carla Groenland Hugo Jacob and Tom Johnston, Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron, accepted by Combinatorial Theory.
We determine the exact value of all antichain saturation numbers in the Boolean lattice {0,1}^n (when n is sufficiently large, proving several conjectures). To do this, we prove that the elements in the union of k chains can always be covered by k disjoint skipless chains.

Extremal and probabilistic questions about permutations

Carla Groenland, Tom Johnston, Jamie Radcliffe and Alex Scott, Short reachability networks.
How many transpositions pi_1,...,pi_k do you need to be able to send the first two positions to any other tuple of distinct positions, i.e. such that for all x<y in {1,...,n}, there is a subsequence 1<=i_1<...<i_j<=k for which the composition pi_{i_1} \circ \dots \circ pi_{i_j} sends 1 to x and 2 to y? We solve this question and study related problems.
Carla Groenland, Tom Johnston, Jamie Radcliffe and Alex Scott, Perfect shuffling with fewer lazy transpositions.
Related to the problem above, what now if each transposition pi_i cannot be freely chosen to be present or not, but rather equals pi_i with a probability p_i and the identity with probability 1-p_i? Each transposition can be assigned a different probability. The resulting composition of random transpositions is now a random permutation. How many are needed to obtain the uniformly random permutation? We provide a construction disproving the natural conjecture that (n choose 2) random transpositions are needed.
Carla Groenland and Tom Johnston, The lengths for which bicrucial square-free permutations exist. Journal publication: PP2021 special issue of Enumerative Combinatorics and Applications.
We characterize for which lengths bicrucial square-free permutations exist via a combination of reductions and computer search.
Carla Groenland, Tom Johnston, Dániel Korándi, Alexander Roberts, Alex Scott and Jane Tan, Decomposing random permutations into order-isomorphic subpermutations, SIAM Journal of Discrete Mathematics.
Given two permutations, what is the largest pattern they have in common? What if the permutations are chosen uniformly at random? And once you have a single pattern in common, can you find more? This motivates the following problem: given two uniformly random permutations, how many parts k do you need, so that the first can be decomposed into s_1,...,s_k and the second into p_1,...,p_k, with p_i order-isomorphic to (''the same as'')p_i for all i? We answer this question (up to log-factors).

Random walks and counting graphic sequences

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston and Alex Scott, Counting graphic sequences via integrated random walks.
We determine the number of graphic sequences (sequences of non-increasing integers that are the degree sequence of some -vertex graph) by proving a new result about random walks.
Juhan Aru, Carla Groenland, Tom Johnston, Bharghav Narayanan, Alexander Roberts and Alex Scott, Exceptional graphs for the random walk, Annales de l’Institut Henri Poincaré, 56(3):2017-2027, 2020.

Independent transversals and cyclically covering subspaces

Carla Groenland, Tomáš Kaiser, Oscar Treffers and Matthew Wales, Graphs of low average degree without independent transversals. Journal version: Journal of Graph Theory, 102:374-387, 2023.
When the average degree is low, it is easier to find independent transversals and these can be guaranteed with entropy compression related methods such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma. We give an example that shows that, unexpectedly, those lower bounds are tight.
James Aaronson, Carla Groenland and Tom Johnston, Cyclically covering subspaces in F_2^n. Journal version: Journal of Combinatorial Theory, Series A, 181:105436, 2021.
A cyclically covering subspace is a linear subspace of F_2^n such that each vector has a cyclic shift (obtained by cyclic permutation of the entries) in the subspace. How small can such a subspace be, more precisely, how large can the codimension be? We show that the codimension is at most 2 whenever n is an Artin primes (a prime such that 1+X+...+X^{n-1} is irreducible in F_2[X]), answering an old question from Peter Cameron modulo Artin’s conjecture. We use various reformulations of the problem to be able to use machinery from additive combinatorics to do so.

Hypercube intersections

In the next two papers, we study intersections between (real) subspaces and the discrete hypercube {0,1}^n. The first studies the possible intersection sizes that a k-dimensional linear subspace can have with the hypercube (disproving two conjectures) and the second studies how many hyperplanes are needed to exactly cover subsets of the hypercube (i.e. their union intersects the hypercube exactly in that subset).

Carla Groenland and Tom Johnston, Intersection sizes of linear subspaces with the hypercube. Journal version: Journal of Combinatorial Theory, Series A, 170:105-142, 2020.
James Aaronson, Carla Groenland, Andrzej Grzesik, Tom Johnston and B. Kielak, Exact hyperplane covers for subsets of the hypercube. Journal version: Discrete Mathematics, 344(9):112490, 2021. [Awarded Editor’s choice 2022]

Page updated

Google Sites

Report abuse