Degree 2 Boolean Functions on Grassmann Graphs

Abstract

We investigate the existence of Boolean degree $d$ functions on the Grassmann graph of $k$-spaces in the vector space ${\mathbb{F}}_q^n$. For $d=1$ several non-existence and classification results are known, and no non-trivial examples are known for $n\ge 5$. This paper focusses on providing a list of examples on the case $d=2$ in general dimension and in particular for $(n,k)=(6,3)$ and $(n,k)=(8,4)$. We also discuss connections to the analysis of Boolean functions, regular sets/equitable bipartitions/perfect 2-colorings in graphs, $q$-analogs of designs, and permutation groups. In particular, this represents a natural generalization of Cameron-Liebler line classes.

21 pages; 1 figure; accepted in the Electronic Journal of Combinatorics

Cited by in corpus (2)

• The degree of functions in the Johnson and q-Johnson schemes
• On degree-$3$ and $(n-4)$-correlation-immune perfect colorings of $n$-cubes