equitable partition

Classifying Cameron-Liebler Sets/Boolean Degree 1 Functions

This week I put two new preprint on the arXiv. Both are on a similar theme, so I will discuss them together. One is with Morgan Rodgers on regular sets of lines in rank 3 polar spaces. The other one is solves a problem which I have been thinking about very regularly since November 2017: The classification of Boolean degree {1} functions (or Cameron-Liebler classes) of {k}-spaces in an {n}-dimensional vector space {V} over the field with {q} elements for {n} large enough (and {q} and {k \geq 2} fixed).

Not only did I (and many other researcher) try to solve this problem for many years, it also turns out that the solution has a very short and concise proof. So for now I am very happy about it. [And please do not find a mistake. Any mistake must be embarrissingly simple.] The problem itself (for {k=2}) goes back to a paper by Cameron and Liebler in 1982, so it is also a reasonably old problem.

(more…)

A Boolean Function with Small Degree and Many Variables

Recently, while working on a research project, I got on a tangent. From this tangent, I got on another tangent and that is what I want to write about today: a very nice Boolean function. This example got rediscovered several times for different reasons and, as I try to emphasize from time, I believe that things that are getting rediscovered many times must be of particular importance.

So let us define our Boolean function. I will give three very similar definitions throughout this post, but I will start with only one. Put {\ell(d) := 3 \cdot 2^{d-1} - 2}. Our Boolean function {F_d: \{ 0, 1\}^{\ell(d)} \rightarrow \{ 0, 1\}} is defined as follows: Put {F_1(x) = x} (as {\ell(1)=1}). For {d > 1}, write {x \in \{ 0, 1\}^{\ell(d)}} as {x=(s,t,y,z)} with {s,t \in \{ 0,1 \}} and {y, z \in \{ 0, 1\}^{\ell(d-1)}}. Then use this rule:

  • If {s=t=1}, then {F_d(1,1,y,z) = F_{d-1}(y)}.
  • If {s \neq t=0}, then {F_d(1,0,y,z) = F_{d-1}(z)}.
  • If {s= t = 0}, then {F_d(0,0,y,z) = 1-F_{d-1}(y)}.
  • If {s \neq t = 1}, then {F_d(0,1,y,z) = 1-F_{d-1}(z)}.

In the following, we list some properties of this function. Many of the concepts here are also discussed in an earlier post of mine.

(more…)

Proving Spectral Bounds With Quotient Matrices

As Anurag Bishnoi likes to point out on his blog, an often overlooked source of wisdom is Willem Haemer’s PhD thesis from 1979. Many of Haemer’s proofs rely on simple properties of partitions of Hermitean matrices. My motivation for this post was a small exercise for myself. I wanted to prove the easy one of the two Cheeger inequalities for graphs using Haemer’s technique. Non-surprisingly, the book “Spectra of Graphs” by Brouwer and Haemers gives this kind of proof.

The K3 times K3 graph with two highlighted equitable partitions.

The K3xK3 graph with two highlighted equitable partitions. Think of the lines as cliques of size 3. This is a picture from my Master thesis many, many years ago.

Earlier on this blog we discussed that there are many different names for equitable partitions. My list from back then is incomplete as (1) I intentionally left out terms such as {T}-designs (not to be confused with {t}-designs) from Delsarte’s PhD thesis, and (2) I realized that for instance Stefan Steinerberger defined a notion of graphical designs which resembles the definition of a {T}-design, while people working on latin squares call them {k}-plexes, for instance see here. For this post just recall the following facts on equitable partitions:
(more…)

Boolean Degree 1 Functions on Association Schemes

This is the announced post on my recent paper with Yuval Filmus on Boolean degree {1} functions on association schemes. The post will focus on what motivates the problem from various points of view.

Before I start, a small remark. I am using latex2wp for the first time in this post. Thanks to Luca Trevisan for providing this nice script.

During this post I avoid using many definition, while I cite things that use all kind of terminology. For this I wrote this blog post as a reference. We will go through the main steps in the paper and focus more on the wider context of the research, so the parts for which there is less space in papers and not enough time in talks.

(more…)

Translating Terminology: Equitable Partitions and Related Concepts

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. (more…)