Degree 2 Boolean Functions on Grassmann Graphs

DOI10.37236/11040MaRDI QIDQ6390503arXivFDO

Authors Jan De Beule, Jozefien D'haeseleer, Ferdinand Ihringer, Jonathan Mannaert

Publication date 8 February 2022

Published in arXiv

Full work available at URL https://doi.org/10.37236/11040

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99) Boolean functions (06E30) Representations of finite symmetric groups (20C30) Combinatorial structures in finite projective spaces (51E20)

arXiv classification

math.CO

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 $ngeq5$. 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.

This page was built for publication: Degree 2 Boolean Functions on Grassmann Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390503)