Degree 2 Boolean Functions on Grassmann Graphs

2022/02/08 by Jan De Beule, De Beule, Jan, Jozefien D’haeseleer +5
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2202.03940

openalex publication_date 2022/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the existence of Boolean degree d functions on the Grassmann graph of k-spaces in the vector space \mathbbF_qⁿ. For d=1 several non-existence and classification results are known, and no non-trivial examples are known for n ≥ 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.

Related

• A Survey of Cameron-Liebler Sets and Low Degree Boolean Functions in Grassmann Graphs
• Boolean degree 1 functions on some classical association schemes
• The classification of Boolean degree 1 functions in high-dimensional finite vector spaces
• On the Chromatic Number of Grassmann Graphs
• Landscape Boolean Functions