Search

The main goal of the thesis is to compare the distinguishing power of known combinatorial and algebraic graph invariants. Using the language of refinement operators (introduced in [32]) we derive known results relating the Weisfeiler-Leman algorithms and the invertible map tests. The former are a well known family of polynomial time algorithms parametrised by some natural number, each defining an equivalence on graphs which over-approximates graph isomorphism. The latter, introduced in [30], are parametrised by a natural number and a set of prime numbers. By generalising the concept of coherent algebras to an arbitrary field, we show that the invertible map tests can be viewed as a representation theoretic generalisation of the Weisfeiler-Leman algorithms. We also show that the equivalences defined by each invertible map test over the set of all prime numbers can be decided in polynomial time. This motivates an open question which could lead to interesting insights into the nature and computational complexity of graph isomorphism, as well as the descriptive complexity of finite graphs. We also use refinement operators to bound the expressive power of an infinitary logic with solvability quantifiers so as to study the relative power of the invertible map tests and known proof systems with algebraic rules; namely, bounded degree polynomial calculus, monomial calculus and Nullstellensatz calculus. These are well studied and have been used in the context of graph isomorphism in [14] and [39]. Our results generalise some of the work in the latter two papers and contribute to a deeper understanding of the apparently weaker Nullstellensatz calculus. More precisely, we show that the distinguishing power of Nullstellensatz calculus is essentially the same as that of monomial calculus. Furthermore, in the case of fields of characteristic 0, we show that Nullstellensatz calculus can simulate polynomial calculus in the case of the graph isomorphism problem; hence, combining this with a results by Grohe et al. [39], it follows that over characteristic 0, all three proof systems have similar distinguishing power to the Weisfeiler-Leman algorithms. Building on recent results by Brachter and Schweitzer [16] we look at the behaviour of the Weisfeiler-Leman algorithms on finite groups. Whilst hinting at potential conditions required to construct families of 2-nilpotent groups with high Weisfeiler-Leman dimension, we also show that the class of 2-nilpotent groups generated by trees has low Weisfeiler-Leman dimension. This naturally leads to the question as to whether classes of graphs with low Weisfeiler-Leman dimension generate classes of 2-nilpotent groups with low Weisfeiler-Leman dimension. Lastly, we show that there is a first-order definable reduction from group isomorphism to the isomorphism problem of Latin square graphs of Cayley tables of groups, and vice-versa. The existence of such a bi-interpretation implies that the Weisfeiler-Leman dimensions of finite groups and Latin square graphs of their Cayley tables have a similar asymptotic behaviour.

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Qm in Qd. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Qd of bounded average degree such that G does not contain a copy of Qm but, for every G' such that G ⊊ G' ⊆ Qd, the graph G' contains a copy of Qm. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2(1-ε)k subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2(1+o(1))ck for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Qm in Qd. That is, we determine the minimum number of edges in a spanning subgraph G of Qd such that the edges of E(Qd)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Qm. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A0 of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A0 percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Qd has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽qnordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (εi)∞i=1 tending to zero such that, for all i ≥ 1, every weak εi-regular partition of W has at least exp(εi-2/25log∗εi-2) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤp such that any two adjacent vertices are mapped to elements of ℤp at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.