Degree 2 Boolean Functions on Grassmann Graphs

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

doi:10.37236/11040

Degree 2 Boolean Functions on Grassmann Graphs

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

Onderzoeksoutput: Article › peer review

6 Citaten (Scopus)

44 Downloads (Pure)

Samenvatting

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-2	English
Artikelnummer	P1.31
Pagina's (van-tot)	1-23
Aantal pagina's	23
Tijdschrift	Electronic Journal of Combinatorics
Volume	30
Nummer van het tijdschrift	1
DOI's	https://doi.org/10.37236/11040
Status	Published - 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:
Copyright 2023 Elsevier B.V., All rights reserved.

Toegang tot document

10.37236/11040Licentie: CC BY-ND

94407734Final published version, 370 KBLicentie: CC BY-ND

Andere bestanden en links

Link naar publicatie in Scopus

1 Talk at an external academic organisation
1 Talk or presentation at a conference

An introduction to Boolean degree d functions in typical association schemes
Jonathan Mannaert (Speaker)
13 mrt. 2023
Activiteit: Talk at an external academic organisation
Low Boolean degree d functions in Grassmann graphs
Jonathan Mannaert (Speaker)
2 sep. 2022
Activiteit: Talk or presentation at a conference

Citeer dit

@article{3465a27731004fa38fdf34b0f3f053ca,

title = "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 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.",

keywords = "Boolean functions, Boolean degree d functions",

author = "{De Beule}, Jan and Jozefien D'haeseleer and Ferdinand Ihringer and Jonathan Mannaert",

note = "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: {\textcopyright} The authors. Copyright: Copyright 2023 Elsevier B.V., All rights reserved.",

year = "2023",

month = feb,

day = "10",

doi = "10.37236/11040",

language = "English",

volume = "30",

pages = "1--23",

journal = "Electronic Journal of Combinatorics",

issn = "1097-1440",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - Degree 2 Boolean Functions on Grassmann Graphs

AU - De Beule, Jan

AU - D'haeseleer, Jozefien

AU - Ihringer, Ferdinand

AU - Mannaert, Jonathan

N1 - 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: Copyright 2023 Elsevier B.V., All rights reserved.

PY - 2023/2/10

Y1 - 2023/2/10

N2 - 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.

AB - 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.

KW - Boolean functions

KW - Boolean degree d functions

UR - http://www.scopus.com/inward/record.url?scp=85147576107&partnerID=8YFLogxK

U2 - 10.37236/11040

DO - 10.37236/11040

M3 - Article

SN - 1097-1440

VL - 30

SP - 1

EP - 23

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P1.31

ER -

Degree 2 Boolean Functions on Grassmann Graphs

Samenvatting

Bibliografische nota

Toegang tot document

Andere bestanden en links

Vingerafdruk

Activiteiten

An introduction to Boolean degree d functions in typical association schemes

Low Boolean degree d functions in Grassmann graphs

Citeer dit