An Upper Bound on the Weisfeiler-Leman Dimension

For the first set of reductions, we employ the concept of a critical configuration:

It turns out that a critical coherent configuration cannot decompose into homogeneously connected components, contain tiny fibers (fibers with at most 3 vertices), or contain $c{K}_{1,d}$ interspaces:

A new technique we develop to deal with fibers that are not tiny is the restorability of fibers: intuitively, when a restorable fiber is removed, there is up to isomorphism a unique way of reinserting the fiber. More formally, we call a union of fibers $ℛ$ restorable if the following holds: All automorphisms of $ℬ≔N(ℛ)$ (so, the union of the neighbors of the fibers in $ℛ$) that extend to automorphisms of $𝔛-ℛ$ also extend to automorphisms of $𝔛[ℬ\cup ℛ]$. We essentially argue that the WL-algorithm, when used as an isomorphism test, is able to deal with $𝔛-ℛ$ and $𝔛[ℬ\cup ℛ]$ separately. Therefore, the WL-dimension of $𝔛$ is the maximum dimension of both subconfigurations $𝔛-ℛ$ and $𝔛[ℬ\cup ℛ]$. With regard to criticality of $𝔛$, we conclude that $𝔛-(ℛ\cup ℬ)$ must be empty:

We now analyze the structure of interspaces between two fibers at least one of which is small. In a series of publications (see [22] and [23] for example) Miyamoto and Hanaki generated all homogeneous coherent configurations up to order $34$. We can observe that the constituents of a homogeneous coherent configuration of order at most $7$ uniquely determine the isomorphism type of the configuration. While this does not necessarily hold for homogeneous coherent configurations of larger orders, the observation carries over to coherent subconfigurations induced by small fibers. Table 1 summarizes the classification.

Regarding interspaces, we next introduce a condensed description, which captures sufficient information to uniquely determine the isomorphism type of small coherent configurations: given an interspace $𝔛[R,B]$ between two (not necessarily distinct) fibers $R$ and $B$, define $T\left(𝔛[R,B]\right)$ to be the collection of isomorphism types of the constituents induced by the basis relations $A$ in a $𝔛[R,B]$ up to isomorphism (omitting reflexive and transposed basis relations).

First, we use the classification of subconfigurations induced by a small fiber to analyze possible interspaces $𝔛[R,B]$ between two small fibers $R$ and $B$. A (slightly lengthy) case analysis leads to a classification, For critical coherent configurations, it is summarized in Table 2. This classification has the following structural consequence:

Our next goal is to describe the possible interspaces between a small fiber $S$ and a fiber $L$ of arbitrary size. Since the large fiber is not bounded in size, there is of course an infinite number of isomorphism types that appear.

Our solution turns out to be rather technical, but the idea is simple. If we forget the structure inside the class $L$, vertices in $L$ will partition into equivalence class depending on their neighborhood in $S$ (taking colors of arcs into account). We now record the isomorphism type of the interspace we obtained by just retaining one representative from each class. However, we also capture, for one vertex $x$ of $L$ what structure the neighborhoods with respect to each color induced in $S$. Due to coherence and the small size of $S$, this structure is the same (up to isomorphism) for every vertex of $L$. Because $S$ has size at most $6$, it turns out that it is essentially sufficient to check the color degrees of $x$ and which neighborhoods induce monochromatic cliques to capture almost all relevant information. (The reader pressed for time may want to skip the specific details in the rest of this subsection and take Proposition 7 simply as a statement that there is some type of classification of the interspaces.)

To formalize this idea and classify the possible interspaces between a small fiber $S$ and a fiber $L$ of arbitrary size, we introduce a new concept: an interspace pattern is a string of information which suffices to characterize the interspace up to a certain equivalence and allows us to extract all combinatorial information relevant for our purposes. The formal definition is slightly technical.

We should emphasize that the sum of the $t_i$ is $|𝔛[L,S]|-1$ and thus we omit exactly one basis relation of the interspaces in the pattern. In fact, in general the missing interspace will not satisfy a clique condition. Also, it is a priori not clear that an interspace always has a pattern of this form we just defined. For $d_j^i=3$, a refined definition distinguishes two versions of the interspace patterns, which we mark with $†$ and $‡$. The reader may find more details on interspace patterns in the full version of the paper [36].

We remark that in our application the small fiber $S$ is restricted to size $4$ or $6$. (It turns out that we do not need to invoke interspace patterns for fibers of size $5$ and $7$ since the second set of reductions described further below allows us to deal with them in simpler manner.) A (again slightly lengthy) case distinction iterates through the possible homogeneous coherent configurations introduced by a small fiber $S$ and the possible connections. We obtain the following classification:

We would like to emphasize that the size of fiber $L$ is arbitrary. In particular, the results classifies an infinite number of isomorphism types of interspaces into finitely many classes.

With the interspace classifications at hand, we examine induced coherent subconfigurations containing a non-dominating small fiber $S$ with regards to criticality. It turns out that certain combinations of interspace patterns occurring simultaneously at one fiber cause $S$ to be restorable. This dictates that certain interspace patterns must appear. It also gives us lower bounds on the number of neighbors certain small fiber $S$ must have.

Assuming that $S$ is a small fiber of size $4$ we have the following restrictions.

We present similar claims for $S$ being a small fiber of size $6$. However, since the amount of possible interspace patterns increases, we first examine the case in which all interspace incident to $S$ in $Q(𝔛)$ have the same interspace pattern. Intuitively, for certain interspace patterns, WL2 captures enough combinatorial information to ensure $S$ is restorable. Overall we obtain the following:

The previous proposition implies that, if fiber $S$ has size $6$ and $|T\left(𝔛[S]\right)|=2$, then there at least two distinct interspace patterns are incident with $S$. If, however, $|T\left(𝔛[S]\right)|>2$, then there is essentially a union of basis relations that induces a graph isomorphic to $C_6$. In this case, up to four distinct interspace patterns may occur in the interspaces incident to $S$ in $Q(𝔛)$. We summarize as follows.

The proofs of most of these claims follow a similar pattern: we start with an induced coherent subconfigurations consisting of multiple fibers and interspaces with a small non-dominating fiber $S$ (and in rare cases multiple non-dominating fibers).

The homogeneous coherent configuration induced by $S$ together with the interspace patterns with its neighbors determines the structure relevant to us. We introduce partition structures to capture this information. It turns out that the automorphisms of the partition structure form a subset of the automorphisms of the fibers neighboring $S$. We can exploit this fact to prove restorability in various cases.

With the preparations complete, we examine the first base case: let $𝔛$ be a critical coherent configuration in which all fibers are small. Due to Proposition 5, either all of its fibers have size $5$, all of them have size $7$, or $𝔛$ consists of size $4$ and size $6$ fibers. In the first two cases, we bound the WL-dimension by a constant due to arguments based on the criticality of $𝔛$.

In the third case, we simplify $𝔛$ by individualizing carefully chosen vertices and restoring coherence and criticality afterwards.

The proof of this proposition heavily relies on Propositions 9 and 11. After their application we are left with simplified critical coherent configuration $𝔛$, whose fibers all have size $4$. By Proposition 9, it is essentially a colored CFI-graph and its $3$-regular quotient graph $Q(𝔛)$ takes the role of the base graph. For two such coherent configurations we observe, by Fomin and Høie’s upper bound for the treewidth of cubic graphs [13], there is a winning strategy for $\frac{n^{\prime }}{6}+o(n^{\prime })$ cops in the cop-and-robbers game played on their quotient graphs of order $n^{\prime }$. We also observe that individualizing a vertex in a fiber $R$ and restoring coherence causes all all vertices of $R$ to become singletons. Combining both observations, we create a winning strategy for spoiler using $\frac{n^{\prime }}{6}+o(n^{\prime })$ pebbles in the pebble game played on the simplified coherent configurations.

We now combine all the three propositions. Note that we can use Proposition 13 inductively. Overall, this establishes an upper bound on the WL-dimension of a critical coherent configuration $𝔛$ with fiber size at most $7$.

In our overall argument, we want to use a bound on the size of the fibers that appear in the coherent configurations. For this purpose we adapt Zemlyachenko’s degree reduction technique (see [5]) to coherent configurations. For the cost of a sublinear number of individualizations we obtain a bound $d$ on the degree of all but the largest relation in each interspace and fiber. Using an adaptation of the argument, we exploit the fact that the degree can be bounded with another sublinear number of individualizations to obtain a bound on the fiber size of the resulting coherent configuration of interest:

Now assume that, in addition to an upper bound $t\in \mathbb{N}$ on the fiber size, the treewidth of $Q(𝔛)$ is bounded as well. We adapt the strategy of the first base case (by individualizing all vertices of $R$ instead of only one vertex) and obtain the following statement:

Our overall goal for local reductions is that after their exhaustive application we obtain a critical coherent configuration structurally similar to the base cases previously discussed. In particular, this means avoiding certain local subconfigurations $𝔖$ of $𝔛$, e.g., interspaces between a large and a small fiber having a certain interspace pattern. We individualize $t$-many vertices and reestablish the coherence and criticality. Most times, this causes the large fibers to split into multiple fibers smaller in size. The result is a critical coherent configuration ${𝔛}^{\prime }$ which does not contain the unwanted local configuration $𝔖$. While we are one step closer to our goal, there are two challenges we need to address:

1. 1.

   Since each individualization increases our bound on the WL-dimension, the configuration ${𝔛}^{\prime }$ must be obtained from $𝔛$ in a controlled manner. We must carefully choose the vertices to be individualized and charge the costs of individualizations to the progress we made towards our goal. To this end, we define the potential function $\tau$ with $\tau (𝔛)≔\frac{3n_{\mathrm{\ell }}+n_s-8k_{\mathrm{\ell }}}{20}$ where parameters $n_{\mathrm{\ell }}$, $k_{\mathrm{\ell }}$, and $n_s$ of $𝔛$ are the number of vertices in large fibers, the number of large fibers, and the number of vertices in small fibers respectively. The progress of a local reduction can be quantified by $\tau ({𝔛}^{\prime })-\tau (𝔛)$, and only local reductions where $\tau (𝔛)\ge t+\tau ({𝔛}^{\prime })$ for $t$ individualizations are eligible.

2. 2.

   While reestablishing the coherence causes fibers contained in $𝔖$ to split, other fibers outside of $𝔖$ might also be affected. So the resulting coherent configuration ${𝔛}^{\prime }$ depends on $𝔛-𝔖$. To dodge this pitfall, we introduce a “monotoniziation” $\tilde{f}$ of the WL-dimension: it maximizes the WL-dimension over all critical coherent configuration whose potential is smaller or equal to a given one.

While we described the main concepts and ideas for the potential function, the machinery of local reductions has more details and some intricacies are not presented here. For the full picture, we refer the reader to the full version [36]. Nevertheless, we summarize that the local reductions roughly adhere to the following blueprint: if $𝔛$ contains $𝔖$, then $WLdim\left(𝔛\right)\le t+\tilde{f}(\tau (𝔛)-t^{\prime })$ where $t^{\prime }\ge t$. To give a flavor of the reductions let us give an example:

In the proof of such local reductions, we often rely on restorability to guarantee lower bounds on the adjacent fibers or the existence of interspace patterns in additional incident interspaces. Let us give another example:

This proposition allows us to bound the treewidth of certain parts of the quotient graph involving large fibers. In general the use of the reductions allows us to reduce our problem to coherent configurations that do not contain various unwanted subconfigurations. Their structure is restricted and this allows us to employ a global argument.

In a configuration $𝔛$ to which no local reduction is applicable, we are guaranteed that certain combinations of interspace patterns involving small fibers do not occur. For example, due to Proposition 18, there is no interspace in $𝔛$ that contains the interspace pattern $(K_{3,3},2)$.

Using our classification results and restorability, we can ensure additional structural properties. To summarize them, we need to distinguish between two types of small fibers: we call a small fiber $R$ relevant, if $|R|\in \{4,6\}$ and there is a constituent in $𝔛[R]$ isomorphic to a clique. It is irrelevant otherwise. The following definition and proposition allows us to formally capture the structure additionally guaranteed.

We need one more structural observation about $t$-reduced configurations to deal with the irrelevant small fibers.

While the notion of $t$-reduced configuration is defined using local properties, there also are ramifications for the global structure of $𝔛$. In fact, the configuration $𝔛$ partitions into large components, small components, and a boundary. Figure 2 visualizes this structure of the quotient graph $Q(𝔛)$. It is as follows.

• $\mathrm{■}$

  Large components contain at least one large fiber but may also include small fibers. The large fibers in a large component induce either a path or a cycle in $Q(𝔛)$ since their color degree is at most $2$. Further, all small fibers within this component are irrelevant. Due to Proposition 22 and being a suitable clique sum, the treewidth of a large component is at most $3$. Since the fiber size of $𝔛$ is at most $t$, the WL-dimension of a large component can be bounded using Proposition 17.

• $\mathrm{■}$

  Small components contain only relevant small fibers that have size $4$ or $6$. Using Proposition 15, an upper bound on their WL-dimension can be established.

• $\mathrm{■}$

  The boundary are the inner fibers of an induced path that connects small and large components. All such fibers are relevant small fibers. The ends of the paths are small fibers in small or large components. Further, the paths have length at most $3$.

We now aim to separate $𝔛$ into the small and large components by individualizing carefully chosen vertices within the paths connecting them. Since the interspaces incident to the fibers of the boundary are guaranteed to have certain interspace patterns, only few individualizations are need to take care of a path.

It remains to show that the overall number of individualizations required in the boundary is not too large: due to properties following from $𝔛$ being $t$-reduced, the size of the boundary is bounded by the number of large fibers. This allows us to charge the individualizations to the large components. After some calculations, we bound the costs of the individualizations by $\frac{2}{20}{n}_{\mathrm{\ell }}$. We thus bound the WL-dimension of $t$-reduced coherent configuration as follows.

When individualizing, generally, the WL-dimension of $𝔛$ is bounded from above by the number of individualizations and the WL-dimension of the resulting coherent configuration.

(Here the $2$ in the maximum is caused by the (possibly repeated) use of WL2 after individualization). Applying this insight to $𝔛$, we iterate through the different cases of Proposition 21 and count the individualizations used in them:

• $\mathrm{■}$

  We choose $t$ depending on $n$ such that $t(n)\in o(n)$ and $t(n)\in \omega (1)$. By Proposition 16 there are $o(n)$-many individualizations such that in the resulting coherent configuration ${𝔛}^{\prime }$ each fiber has size at most $t$.

• $\mathrm{■}$

  The number of individualizations used in the local reductions to obtain the $t$-reduced, critical coherent configuration ${𝔛}^{\prime \prime }$ is bound by $\tau ({𝔛}^{\prime })-\tau ({𝔛}^{\prime \prime })$.

• $\mathrm{■}$

  Finally, Proposition 24 guarantees that there is a bound on the WL-dimension of the $t$-reduced, critical coherent configuration ${𝔛}^{\prime \prime }$. We obtain $WLdim\left({𝔛}^{\prime \prime }\right)\le \tau ({𝔛}^{\prime \prime })+o(n)$.

Overall, this yields the following:

This concludes the proof sketch of the upper bound (Theorem 1).