Degree 2 Boolean Functions on Grassmann Graphs

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

Onderzoeksoutput: Articlepeer review

18 Downloads (Pure)


We investigate the existence of Boolean degree d functions on the Grassmann graph of k-spaces in the vector space F^n_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.
Originele taal-2English
Pagina's (van-tot)1-23
Aantal pagina's23
TijdschriftElectronic Journal of Combinatorics
Nummer van het tijdschrift1
StatusPublished - 10 feb 2023

Bibliografische nota

Funding Information:
We thank Sam Adriaensen, John Bamberg, and Alexander L. Gavrilyuk for very helpful comments. We thank Yuval Filmus for several suggestions, including the list in §3 and Conjecture 16. We thank Yuriy Tarannikov for informing us about [10] and [45]. We thank the referee for their careful reading of the document. The second and third authors are each supported by a postdoctoral fellowship of the Research Foundation – Flanders (FWO).

Publisher Copyright:
© The authors.

Copyright 2023 Elsevier B.V., All rights reserved.


Duik in de onderzoeksthema's van 'Degree 2 Boolean Functions on Grassmann Graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit