Permutation Groups, Analysis of Boolean Functions, Finite Geometry, Coding Theory and Algebraic Graph Theory

Important mathematical concepts get reinvented many times. In my recent work with Yuval Filmus we explored objects that are called (in random ordering) Boolean degree 1 functions, Cameron-Liebler line classes, equitable partitions, completely regular strength 0 codes with covering radius 1, intriguing sets, perfect colorings, sets with dual width 1, tactical decompositions or tight sets — all depending on the context and who you ask. While the article with Yuval explains to some extent how these notions connect, a research article does not seem to be the right format to explain all concepts in sufficient detail. This post tries to amend this. It also prepares a future post which will elaborate my research with Yuval in more detail.

Algebraic Graph Theory

Let [latex]X[/latex] be a graph on [latex]v[/latex] vertices [latex]V(X)[/latex]. The adjacency matrix [latex]A[/latex] of [latex]X[/latex] is the [latex]v \times v[/latex] matrix indexed by the vertices of [latex]X[/latex] such that [latex]A_{xy} = 1[/latex] if x and y are adjacent and [latex]A_{xy} = 0[/latex] otherwise. In the following we stick to the assumption that [latex]X[/latex] is a regular graph, so every vertex has the same number of neighbors. This is equivalent to saying that the all-ones vector [latex]j[/latex] is an eigenvector of [latex]A[/latex]. The matrix [latex]A[/latex] is symmetric, so we find many other eigenspaces over the reals and this is what this post is about.

Three Examples

We will mostly work with the following three examples throughout this document.

Example 1

Let [latex]J(n, k)[/latex] be the graph with the k-element subsets of an n-element set as vertices. Two vertices are adjacent if they meet in [latex]k-1[/latex] elements. This is the Johnson graph.

Example 2

Let [latex]q[/latex] be a prime power. Let [latex]J_q(n, k)[/latex] be the graph with the k-spaces of an n-dimensional vector space over [latex]\mathbb{F}_q[/latex] as its vertices. Two vertices are adjacent if they meet in a subspace of dimension [latex]k-1[/latex]. This is the Grassmann graph or q-Johnson graph.

Example 3

Let [latex]\overline{D}_n[/latex] be the graph with the elements of the symmetric group [latex]S_n[/latex] as vertices. We see [latex]S_n[/latex] as a permutation group acting naturally on [latex]\{1, \ldots, n\}[/latex]. Two vertices x, y are adjacent if [latex]x y^{-1}[/latex] has exactly n-2 fixed points. This graph is known as the transposition graph. I do not know if this graph has some special name, but the graph on the same set of vertices, where two vertices are adjacent if [latex]x y^{-1}[/latex] has no fix points, is called derangement graph.

Eigenspaces

All eigenspaces of the first two examples were described in Philippe Delsarte’s PhD thesis in 1973. The third example is a Cayley graph on [latex]S_n[/latex], which means that it is well-known that one can obtain its eigenvalues from the character table (so the representation theory) of [latex]S_n[/latex].

Equitable Partitions

An equitable partition is a partition of [latex]V(X)[/latex] into [latex]m[/latex] parts [latex]X_1 + \ldots + X_m[/latex] such that there exist constants [latex]b_{ij}[/latex] such that every vertex in [latex]X_i[/latex] has exactly [latex]b_{ij}[/latex] neighbors in [latex]X_j[/latex]. Another word for equitable partition is perfect coloring. The central property of equitable partitions is the following: The eigenvalues of the matrix [latex]B = ( b_{ij} )_{i,j}[/latex] are also eigenvalues of the adjacency matrix [latex]A[/latex]. The existence of equitable partitions is a question that is investigated on its own for many interesting graphs, but I believe that the notion was invented as an easy way of determining eigenvalues of a graph.

Warning: The term equitable partition is also used by Janos Pach for a completely different concept which I will not go into. For example this paper talks about this different usage of the word.

Example 4

Let [latex]X_1[/latex] be the set of all k-sets containing 1 and [latex]X_2[/latex] the set of all the remaining k-sets. Then [latex]|X_1| = \binom{n-1}{k-1}[/latex] and [latex]|X_2| = \binom{n-1}{k}[/latex]. It is an easy exercise to verify that this is an equitable partition with [latex]b_{11} = (k-1)(n-k)[/latex], [latex]b_{12} = n-k[/latex], [latex]b_{21} = k[/latex], and [latex]b_{22} = k(n-k-1)[/latex]. The eigenvalues of [latex]B[/latex] are [latex]k(n-k)[/latex] (this is the degree of the graph) and [latex]k(n-k)-n[/latex] — the second largest eigenvalue of [latex]A[/latex].

Example 5

Let [latex]X_1[/latex] be the family of all k-sets containing 1 and 2, [latex]X_2[/latex] the family of all k-sets containing 1 or 2, and [latex]X_3[/latex] the remaining k-sets. Again, we can easily verify that this is an equitable partition. This time [latex]b_{11} = (k-2)(n-k)[/latex], [latex]b_{12} = 2(n-k)[/latex], [latex]b_{13} = 0[/latex], [latex]b_{21} = k-1[/latex], [latex]b_{22} = (k-1)(n-k-1) + 1[/latex], [latex]b_{23} = n-k-1[/latex], [latex]b_{31} = 0[/latex], [latex]b_{32} = 2k[/latex], [latex]b_{33} = k(n-k-2)[/latex]. The eigenvalues of [latex]B[/latex] are then [latex]k(n-k)[/latex], [latex]k(n-k)-n[/latex] and [latex]k(n-k) – 2n[/latex].

You see the pattern? So let’s jump ahead.

Example 6

Let [latex]X_j[/latex] be the family of all k-sets meeting [latex]\{ 1, \ldots, k \}[/latex] in [latex]k-j[/latex] elements. Then [latex]X_0, X_1, \ldots, X_k[/latex] is an equitable partition. This partition yields directly all the eigenvalues of the Johnson graph which are [latex]k(n-k)-ni[/latex] for [latex]i = 0, \ldots, k[/latex].

Distance-regular graphs

You might have noticed that the last example just partitioned the vertices of [latex]J(n, k)[/latex] by their distance to a fixed vertex. This is a distance partition. This works because the graph [latex]J(n, k)[/latex] is a distance-regular graph.

Example 7

Let [latex]X_1[/latex] be the set of k-spaces in [latex]J_q(n, k)[/latex] containing a fixed 1-space [latex]p[/latex] and let [latex]X_2[/latex] be the set of k-spaces not containing [latex]p[/latex]. Then it is easy to see that we again have an equitable partition. The graph [latex]J_q(n, k)[/latex] is also distance-regular, so we can also choose the distance partition.

Example 8

Let [latex]X_1[/latex] be the set of permutations of [latex]S_n[/latex] which map a to b and let [latex]X_2[/latex] be the set of remaining permutations. Again this defines an equitable partition of [latex]\overline{D}_n[/latex]. Here [latex]b_{11} = (n-1)(n-2)/2[/latex], [latex]b_{12} = n-1[/latex], [latex]b_{21} = 1[/latex], and [latex]b_{22} = n(n-1)/2-1[/latex].

In this case we cannot use the distance partition to obtain all the eigenvalues as the graph [latex]\overline{D}_n[/latex] is not distance regular. If we instead fix a vertex [latex]x[/latex] and partition [latex]V(\overline{D}_n)[/latex] by the conjugacy class of [latex]xy^{-1}[/latex], then again we obtain an equitable partition.

Association Schemes

I will not define association schemes here (see Chris Godsil’s nice notes on this for more details), but this seems to be the appropriate time to remark that when you can fix any vertex x and partition the remaining vertices y according to their relation to x (by distance or conjugacy class or something similar) and this is an equitable partition, then this is usually an association scheme. This algebraic structure is investigated in many ways by algebraists and used in many ways by combinatorialists.

Ordering the Eigenspaces

We saw that for [latex]J(n, k)[/latex] we have a natural ordering of the eigenspaces: We already know that the all-ones vector is an eigenvector, so this is our trivial eigenspace [latex]V_0[/latex]. If we take the equitable partition induced by partitioning [latex]V(J(n, k))[/latex] into everything containing a fixed element p and everything not containing p, then we obtain a second eigenvalue with its corresponding eigenspace [latex]V_1[/latex]. Let [latex]p^+[/latex] denote the indicator vector of [latex]p \in \{ 1, \ldots, n \}[/latex], that is [latex](p^+)_x[/latex] is 1 if [latex]p \in x[/latex] and 0 otherwise. Indeed, [latex]V_0+V_1[/latex] is spanned by [latex]\{ p^+: p \in \{ 1, \ldots, n \}\}[/latex]. Next [latex]V_0+V_1+V_2[/latex] is spanned by the indicator vector of pairs of elements [latex]\ell[/latex], [latex]V_0+V_1+V_2+V_3[/latex] by triples and so on.

The graph [latex]J_q(n, k)[/latex] behaves in a very similar way, just that p is a 1-space, [latex]\ell[/latex] a 2-space and so on: the eigenspaces [latex]V_0 + V_1 + \ldots + V_t[/latex] are spanned by the indicator vectors of t-spaces. This is a general property for many highly symmetric graphs such as distance-regular graphs.

This no longer works for [latex]\overline{D}_n[/latex] for various reasons, but it is still natural to denote the non-trivial eigenspace corresponding to the equitable partition in Example 8 by [latex]V_1[/latex] (or by some union of eigenspaces if it yields a partition into more parts). And there is a standard way of obtaining a partial ordering of the eigenspaces, starting with [latex]V_1[/latex], but that will not concern us too much.

The Strength and Covering Radius of a Set

Let [latex]\mathcal{F}[/latex] be a subset of vertices of our graph [latex]X[/latex] with some natural partial ordering of eigenspaces. For simplicity assume that [latex]X[/latex] is distance regular and has a proper ordering of eigenspaces [latex]V_0 + V_1 + V_2 + \ldots + V_k[/latex] (a so-called [latex]Q[/latex]-polynomial association scheme). We write f for the characteristic vector of [latex]\mathcal{F}[/latex], so [latex]f_x = 1[/latex] if [latex]x \in \mathcal{F}[/latex] and [latex]f_x = 0[/latex] otherwise. Clearly, we can write [latex]f[/latex] as a sum of eigenvectors [latex]f = v_0 + v_1 + \ldots + v_k[/latex], maybe some of these equal to 0. The strength of [latex]\mathcal{F}[/latex] is the largest s such that [latex]v_i = 0[/latex] for all [latex]i \in \{ 1, \ldots, s \}[/latex] (with [latex]s = 0[/latex] if [latex]v_1 \neq 0[/latex]). The set [latex]\mathcal{F}[/latex] is a completely regular if it is an equitable partition. The covering radius of [latex]\mathcal{F}[/latex] is the number of non-trivial eigenvalues in the equitable partition.

We limit ourselves to distance-regular graphs which makes things easier. For example for [latex]\overline{D}_n[/latex] all these definition would be slightly more complicated (that is why I am not presenting them).

Example 9

Our Example 4 has has strength 0 and covering radius 1. Our Example 5 has strength 0 and covering radius 2.

Example 10

It is well-known that a perfect code of [latex]J(n, k)[/latex] is an example for a completely regular set. In fact, Delsarte defined the notion of completely regular as a generalization of perfect codes. Perfect codes are very rare, for example there are only three perfect codes in [latex]J(n, k)[/latex]. See Natalia Silberstein’s Master thesis for a nice argument for this.

Analysis of Boolean Functions

Up to now, we mostly thought of our set [latex]\mathcal{F}[/latex] as a vector [latex]f[/latex] with entries 0 and 1. Alternatively, we can think of f as a function from [latex]V(X)[/latex] to [latex]\{ 0, 1 \}[/latex]. That is a Boolean function. Traditionally, the term Analysis of Boolean Functions is only used if one works in the hypercube, so [latex]V(X) = \{ 0, 1 \}^n[/latex], but in the last years there is some interest in transferring results to other highly symmetric association schemes (our introduction here provides a few references).

Warning: We think about the reals. In some areas of Boolean analysis — in particular bent functions — one works over the binary field.

Again, Degree and Eigenspaces

Recall that in [latex]J(n, k)[/latex] the Boolean function [latex]p^+[/latex] is defined by [latex]p^+(x) = 1[/latex] if and only if [latex]p \in x[/latex]. Then we can write any function [latex]f: V(J(n, k)) \rightarrow \mathbb{R}[/latex] as a polynomial in the variables [latex]p^+[/latex]. In other words, we have [latex]f = c + \sum_p c_p p^+ + \sum_{p_1, p_2} c_{p_1, p_2} p_1^+ p_2^+ + \ldots[/latex]. Now we can ask for all the Boolean functions of degree 1. So we have [latex]f = c + \sum_p c_p p^+[/latex] and the image of f is in [latex]\{ 0, 1 \}[/latex]. But recall that above we learned that the [latex]p^+[/latex] span [latex]V_0 + V_1[/latex]. Hence, Boolean degree 1 functions are just 0-1 vectors in the subspace [latex]V_0 + V_1[/latex].

Whenever we have some form of lattice where something can take a role similar to the elements of [latex]\{ 1, \ldots, n \}[/latex], we can define Boolean degree t functions (or more, generally, degree s functions) in a similar way. For [latex]J_q(n, k)[/latex] these are the 1-spaces. For [latex]\overline{D}_n[/latex] these are all the maps from a to b.

When using linear algebra methods, then one often investigates the decomposition of f into eigenvectors, that is [latex]f = v_0 + v_1 + \ldots + v_k[/latex] as above. In the analysis of Boolean functions it is common to denote this as Fourier transform of [latex]f[/latex].

Different points of view are always helpful for approaching a research problem. In the following two examples for this.

Example 11

Consider the hypercube, that is the graph of all subsets of [latex]\{ 1, \ldots, n \}[/latex]. What are the Boolean degree 1 functions? Just [latex]0, 1, p^+, 1-p^+[/latex]. Seen as a degree 1 polynomial this is an easy exercise. Seen more generically as a 0-1 vector in [latex]V_0 + V_1[/latex], this is slightly harder to see.

Example 12

Now what non-trivial properties has a Boolean degree 1 function f on [latex]J_q(4, 2)[/latex]. A very straightforward linear algebra argument shows you that [latex]q^2+q+1[/latex] divides the size of f. When just writing f as a degree 1 polynomial I do not know how to see this easily — except of course by emulating the linear algebra argument.

Warning: Boolean degree 1 functions are not a strict subset of equitable partitions. It can be that the [latex]p^+[/latex] span more than one eigenspace. Also if the characteristic vector of a set lies in more than one non-trivial eigenspace, then there is no guarantee that it is an equitable partition.

Permutation Groups and Cameron-Liebler sets

Next let us explain the word Cameron-Liebler line class. Consider again [latex]S_n[/latex] canonically acting on [latex]\{ 1, \ldots, n \}[/latex]. Any subgroup H of [latex]S_n[/latex] partitions the set of k-sets on [latex]\{ 1, \ldots, n \}[/latex] into orbits. In particular, we have some number A of orbits on 1-sets and some number B of orbits on 2-sets. It is easy to see that [latex]A \leq B[/latex]. But when do we have equality? It turns out that there are only two cases: either [latex]H = S_n[/latex] with [latex]A = B = 1[/latex] or [latex]H[/latex] is the stabiliser of a 1-set and [latex]A = B = 2[/latex]. You might realize that the second example is the equitable partition from Example 4. That describes a Boolean degree 1 function. Hence, asking for equality asks for Boolean degree 1 function which are induced by subgroups of [latex]S_n[/latex].

In 1982 Cameron and Liebler asked the same question for [latex]J_q(n, k)[/latex]. Here A is the number of orbits of the projective general linear group [latex]PGL(n, q)[/latex] on 1-spaces and B the number of orbits on 2-spaces. Again, when do we have equality in [latex]A \leq B[/latex]? There are a few obvious examples and Cameron and Liebler conjectured that these are all examples (more on this in the announced future post). Again, any example corresponds to a Boolean degree 1 function. There are surprisingly many non-obvious example for Boolean degree 1 functions and in the research in finite geometry around this topic, the term Cameron-Liebler line class (or some variation of it) is well-established.

Tactical Decompositions

In general, taking subgroup of a collineation group of graph is a natural way of obtaining equitable partitions. The keyword here is tactical decomposition (of (sub)group orbits). The process is very straightforward: suppose that you have a vertex transitive graph G with automorphism group Aut(G). Take any subgroup H of Aut(G). Then the orbits of H on vertices define an equitable partition. This is a natural of way looking for example for equitable partitions with special described properties. Indeed, the many known examples for non-trivial Boolean degree 1 functions in [latex]J_q(n, k)[/latex] were found by combining unions of orbits for a suitable subgroup H. This is called finding a tactical decomposition. There are many nice text on tactical decompositions, for instance this one by Anton and Dieter Betten.

Design Orthogonality

For the sake of completeness, I want to mention that sometimes all the objects above are defined by using design orthogonality. To my knowledge this concept goes (again!) back to Delsarte. This definition is very specialized. For example for [latex]J(n, k)[/latex], n a multiple of k, and [latex]n/k \geq 3[/latex], it goes as follows: Let g be the characteristic functions of [latex]\{ 1, \ldots, n \}[/latex] into k-sets. A (Boolean) function f has degree 1 if and only if it meets [latex]g^h[/latex] in a constant number of elements (for h being an element of [latex]S_n[/latex] acting canonically).

Example 13

Let [latex]\mathcal{F}[/latex] be the family of all vertices of [latex]J(n, k)[/latex] which contain 1. If k divides n, then each partition of [latex]\{ 1, \ldots, n \}[/latex] contains exactly one element of [latex]\mathcal{F}[/latex].

Finite Geometry: Tight Sets, Intriguing Sets, m-Ovoids …

Cameron-Liebler line class is not the only word for the same object in finite geometry. The collinearity graph G of a finite classical polar space or a generalized quadrangle is strongly regular which implies that the adjacency matrix has only three eigenspace, so we can decompose as [latex]V_0 + V_1 + V_2[/latex]. A coclique of G which satisfies the ratio bound (also called Hoffman’s bound) with equality (this is my obligatory reference to my WordPress username) lies in [latex]V_0 + V_2[/latex] (notice that is is debatable what the natural ordering of the eigenspaces is). This is an equitable partition and an equitable partition in [latex]V_0 + V_2[/latex] is usually called m-ovoid. Similarly, an equitable partition in [latex]V_0 + V_1[/latex] is called x-tight set. The general umbrella term for an equitable partition is intriguing set. De Bruyn and Suzuki define an intriguing set more generally as an equitable partition with two parts for any regular graph, so any 0-1 vector in [latex]V_0 + V_i[/latex].

Some Concluding Words

Originally, I planned on just writing a blog post about my paper with Yuval. Then I met Dirk Frettloh during Kolkom 2018 recently. He gave a talk on equitable partitions for 3-, 4-, and 5-regular graphs. For these graphs he provided an exhaustive list of all possible matrices B for equitable partitions with two parts. There I claimed to him that my article mentions some of the words which are used in specific settings to describe equitable partitions. Sadly, I realized still during the conference (looking at our article again) that we did not even mention the word equitable partition. This blog post is aimed at amending this situation. Also I am sure that many of the things above were rediscovered and investigated independently a few more times.

It is (at least for me) exhausting to cover all these terms and translate them correctly. I apologize for any imprecision. Please let me know in the comments. This is a blog post, so that I can easily fix things.

Acknowledgements: I thank John Bamberg for suggesting that I add the term “tactical decomposition”, thanks to Karen Meagher for pointing out that Example 3 is the transposition graph, and thanks to Dirk Frettloh for correcting my (previously unintentionally slightly misleading) summary of his paper. Also thanks to several readers who pointed out minor typos.