A Survey of Cameron-Liebler Sets and Low Degree Boolean Functions in Grassmann Graphs

Ferdinand Ihringer

REVIEW 2 major objections 5 minor 111 references

A Survey of Cameron-Liebler Sets and Low Degree Boolean Functions in Grassmann Graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read One association-scheme language describes low-degree Boolean functions and Cameron-Liebler sets in Hamming, Johnson, and Grassmann graphs.

desk verdict A useful cross-disciplinary survey with two fixable but real internal errors that should be cleaned up before it becomes the go-to reference. read the letter →

arxiv 2411.16288 v2 pith:4AVARVOU submitted 2024-11-25 math.CO cs.DM

Ferdinand Ihringer This is my paper · ORCID

classification math.COcs.DM MSC 05E3005B0505D0505C50

keywords Cameron-Lieblersetslow-degreeBooleanfunctionsGrassmanngraphsassociationschemesDelsartetheoryHammingschemeJohnsonjuntatheorems

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This survey's thesis is that association schemes and Delsarte theory give a single language for two topics usually studied separately: low-degree Boolean functions on the hypercube and its slices, and Cameron-Liebler sets in finite projective geometry. In that language, degree $d$ means living in the first $d+1$ eigenspaces of the scheme, and the known results line up: degree-1 functions on the Hamming and Johnson graphs are only dictators and their complements, while the Grassmann graph $J_q(4,2)$ admits many exceptional degree-1 examples, which the survey tabulates. The paper also records size bounds, divisibility conditions, and the structure theorem behind the 2-to-2 Games proof as facets of the same spectral picture. A reader would care because this is the closest existing statement that Boolean function analysis and finite geometry are studying the same objects.

What carries the argument

The central object is the association scheme of the relevant graph: a decomposition of the ambient vector space $\mathbb{C}^X$ into common eigenspaces $V_0, V_1, \ldots, V_m$ of the adjacency matrices, with $V_0$ spanned by the all-ones vector. A Boolean function has degree $d$ exactly when its characteristic vector lies in $V_0 + \cdots + V_d$, and Delsarte's linear programming bound checks orthogonality to eigenspaces using only the small $Q$-matrix rather than the full projection. For the Grassmann case, the workhorse is a weighted function $g_{P,H}$ on lines of $\mathrm{PG}(3,q)$ whose design-orthogonality with any degree-1 set yields an equation relating the size parameter $x$ to counts of lines through a point, in a hyperplane, and in both, with the possible line patterns strongly restricted; tactical decompositions and Block's lemma explain why group actions produce such sets.

What would settle it

Count the lines in the Section 5.1.1 construction: the four listed types total $(q^2+1)(q+2)$ lines, but $\mathrm{PG}(3,q)$ has $(q^2+1)(q^2+q+1)$ lines, so the types do not partition the line set; checking whether an omitted line type is forced into the example would settle whether the construction stands. The table and text also disagree on whether the stabilizer is $\mathrm{O}^+(4,q)$ or $\mathrm{O}^-(4,q)$, and resolving that against the definition of the quadratic form would settle the inconsistency.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that a common formalism---the eigenspace decomposition of a cometric association scheme, together with Delsarte's linear programming bound and design-orthogonality---correctly organizes the classification results on Boolean degree-1 functions and Cameron-Liebler sets. In the Hamming scheme and the Johnson scheme, degree-1 Boolean functions are trivial; the Friedgut-Kalai-Naor theorem and its slice analogue say that near-degree-1 functions are close to unions of few stars. In the Grassmann scheme, the paper presents the known landscape: for $q \in \{2,3,4,5\}$ and for $|n-2m|$ sufficiently large all degree-1 functions are trivial, but in $J_q(4,2)$ there are many exceptional families, listed with their parameters, sizes, and stabilizers, including the quadric, derived, projective, affine, and sporadic examples. The survey thereby presents all known non-trivial degree-1 behavior as concentrated in this one Grassmann setting.

Load-bearing premise

The load-bearing premise is that the survey's table of exceptional examples in the Grassmann graph $J_q(4,2)$ is complete and correct as written; if the Section 5.1.1 construction's list of line types does not actually cover all lines, the claimed inventory fails.

Editorial extensions

If this is right

If the survey's organization is right, degree-1 in the Hamming and Johnson schemes is completely understood, with FKN-type stability showing approximate degree-1 functions are close to dictators or small unions of stars.
For the Grassmann scheme, all currently known non-trivial degree-1 sets lie in $J_q(4,2)$, and for $q \in \{2,3,4,5\}$ or for $|n-2m|$ sufficiently large every degree-1 function is one of the trivial examples.
The divisibility condition that a certain gcd of Gaussian coefficients divides $|Y|$ for degree-$d$ functions supplies the correct size restriction across the Johnson and $q$-Johnson schemes.
The Khot-Minzer-Safra theorem becomes a low-degree structure theorem for $J_2(n,m)$: a set with small expansion has significant weight on low-degree eigenspaces and contains a dense interval of subspaces between some $R$ and $S$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the Section 5.1.1 construction's census of lines should be checked before the inventory is treated as closed, since the listed line types appear not to cover all lines of $\mathrm{PG}(3,q)$.
The survey suggests that any q-analogue of the FKN theorem for Grassmann graphs must explicitly exclude small $(n,m)$, because $J_q(4,2)$ already contains many counterexamples to a naive stability statement.
A testable extension is to look for hypercontractivity on Grassmann graphs through their induced bilinear-forms subgraphs, since the paper notes hypercontractivity is available there but not on the Grassmann scheme itself.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: the survey earns its keep as a map, not as a source of new results. It fills a real gap by putting Cameron-Liebler sets, Boolean degree functions, and their relatives under one association-scheme framework, and its inventory of exceptional degree-1 examples in Jq(4,2) is useful. But two internal errors need correcting. The reader's line-count objection to the Bruen-Drudge census in §5.1.1 is a misfire. Items (i) and (ii) are binomial coefficients—each is (q^2+1 choose 2)—and the four items sum exactly to the total (q^2+1)(q^2+q+1) lines. That part is fine. The real problems are elsewhere. The prose says the Bruen-Drudge example has stabilizer 'the finite simple group of type O+(4,q)', while Table 1 correctly says O^-(4,q). The quadratic form in question has non-square discriminant, so the elliptic group is the one that acts; O^+(4,q) is not simple anyway. This contradiction sits in the central inventory, so it's load-bearing. It looks like a one-line typo, but a reference survey cannot carry it. Second, the Hamming graph eigenvalues in Example 2.1 are corrupted as printed: θ_j = q(n−j)−d with dimension binom(d,j)(q−1)^j. The correct formulas are θ_j = (q−1)n − qj with multiplicity binom(n,j)(q−1)^j. As written, 'd' appears where only 'n' makes sense. Also fixable, but it will mislead a newcomer. The rest reads as careful and honest. The author credits the right people, the cross-community translations are accurate, and the discussion of FKN, Nisan-Szegedy, and the Khot-Minzer-Safra theorem is reliable. The paper leans on the author's own results, but he actually proved a good chunk of what is surveyed, so that is not a problem. Who benefits: researchers or students who want to see why finite geometry and Boolean function analysis are converging, and where the open problems sit. The central structure is sound. I would send it to a serious referee, ask for verification of the Table 1 group entries and the Section 2 formulas, and accept after those fixes. I'd cite it once it is cleaned up. Recommendation: give it a proper referee; the errors are minor but real, and the survey deserves to be a standard entry point.

Referee Report

2 major / 5 minor

Summary. This survey aims to present known results on Cameron-Liebler sets and low-degree Boolean functions for Hamming graphs, Johnson graphs, and Grassmann graphs from a unified association-scheme and Delsarte-theory perspective. It covers spectral preliminaries, design-orthogonality, equitable partitions, the FKN theorem and its analogues, Nisan-Szegedy-type junta bounds, the Khot-Minzer-Safra theorem, the classification of degree-1 functions on Grassmann graphs, and an inventory of exceptional degree-1 examples in J_q(4,2). The paper is primarily an exposition with a broad bibliography, and its main value would be as a reference connecting finite geometry, Boolean function analysis, coding theory, and cryptography.

Significance. If the reference-level details are correct, this survey fills a genuine need: it collects recent results from several communities that rarely cite each other and phrases them in a common association-scheme language. The table of exceptional degree-1 examples in J_q(4,2), the summary of small-q classification results, and the discussion of the Khot-Minzer-Safra theorem are potentially useful entry points for both finite geometers and Boolean-function analysts. I verified that the line census in §5.1.1 is arithmetically consistent when items (i) and (ii) are read as binomial coefficients, so the line-count objection does not land. However, the manuscript contains internal inconsistencies in exactly the places a reader would use as reference, most importantly the stabilizer-group contradiction in the central inventory and the corrupted eigenvalue formula in the spectral preliminaries.

major comments (2)

[§5.1.1 / Table 1] The stabilizer of the Bruen-Drudge family is stated in §5.1.1 as "the finite simple group of type O+(4,q)", while Table 1 lists O-(4,q) and §5.1.2 refers to "a point in O-(4,q)". The displayed quadratic form Q has non-square discriminant, its zero set has q^2+1 points, and the group fixing such a quadric is the elliptic orthogonal group O-(4,q); moreover O+(4,q) is not a simple group for any q, so the phrase "finite simple group of type O+(4,q)" is internally impossible. Since Table 1 is the promised complete inventory of exceptional degree-1 examples in J_q(4,2), this contradiction prevents a reader from trusting the inventory without returning to the primary sources. Please correct the prose or the table and verify the remaining group entries in the table.
[§2.1, Example 2.1] The Hamming graph eigenvalue formula as rendered is theta_j = q(n-j)-d with dimension d choose j times (q-1)^j, where d is not defined and the formula is not the spectrum of H(n,q). The correct value is theta_j = q(n-j)-j, equivalently n(q-1)-qj, with multiplicity n choose j times (q-1)^j. This is part of the common spectral dictionary on which the survey's unified framework relies, so the formula should be corrected; if this is an artifact of the rendering, the displayed version in the manuscript should be fixed.

minor comments (5)

[§2.2] In the inversion formula for the idempotents, the sum is written as sum_{i=1}^m Q_{ij}A_i; it should run from i=0 to m, since E_0 = v^{-1}J is part of the basis of minimal idempotents.
[§2.1, Examples 2.2 and 2.3] The eigenvalue index ranges are stated as 0 ≤ j ≤ n for both the Johnson and Grassmann graphs, but these graphs have m+1 distinct eigenvalues; the range should be 0 ≤ j ≤ m.
[§5.1.4] The sentence "Then the set consists of the following is an Boolean degree 1 function with x = 7" should be rephrased, for example as "Then the set consisting of the following lines is a Boolean degree 1 function with x = 7."
[§5.2] The phrase "show the that the non-trivial examples" contains a typo and should read "show that the non-trivial examples".
[Table 1] The abbreviation "pt.-stab." in the group column should be expanded or defined in the table caption, since it is not explained elsewhere in the text.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the survey is expository and its cited results, including the author's own [73] and [54], are independent published theorems.

full rationale

This paper is a survey, not a derivation. Its stated aim is to present selected results on Cameron-Liebler sets and low-degree Boolean functions from an association-scheme viewpoint, and no equation in the paper is fitted to data or defined in terms of a quantity the paper itself produces. The only appearances of the author's own work are citations to published theorems—[54] in Theorem 5.1, [73] in Theorem 5.2, and [74] in Theorem 5.4—which are used as background results with external proofs, not as premises that make the survey's organization true by construction. The rephrasing of the FKN theorem in Theorem 3.2 and the equivalence between low-degree weight and spectral projection in Section 5.3.1 are translations of established results, not circular redefinitions. I therefore find no self-definitional, fitted-input, or self-citation-load-bearing step. (Separately noted, possible factual inconsistencies such as the O^+(4,q)/O^-(4,q) wording in Section 5.1.1 are correctness concerns, not circularity.)

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The survey introduces no free parameters and no new entities. It relies on classical association-scheme theory and on the correctness and representativeness of the cited literature, including several of the author's own papers.

assumptions (4)

standard math The Hamming, Johnson, and Grassmann schemes are metric and cometric association schemes with known eigenvalue formulas.
The survey's framework depends on the classical spectral theory of these schemes, cited to Brouwer-Cohen-Neumaier [12] in Section 2.2.
standard math A Boolean function on any of the three families has degree at most d if and only if its characteristic vector lies in V0 + ... + Vd.
Stated in Section 2.3 as 'deg(fY) <= d if and only if fY in V0 + V1 + ... + Vd in the usual cometric ordering'; this equivalence is the translation device between finite geometry and Boolean analysis.
domain assumption The theorems and constructions cited from the literature, including the author's own Theorem 5.2 from [73], are correct as stated.
A survey propagates the errors of its sources; the paper does not reprove these results.
domain assumption The selection of results in the survey is representative of the current state of the art in both communities.
Stated in Section 1 as 'Our aim is a survey of selected results'; selective coverage can bias the reader's picture.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Survey of Cameron-Liebler Sets and Low Degree Boolean Functions in Grassmann Graphs." pith.science (2026). https://pith.science/paper/4AVARVOU

@misc{pith2026241116288,
  author       = {Pith},
  title        = {Pith review of: A Survey of Cameron-Liebler Sets and Low Degree Boolean Functions in Grassmann Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4AVARVOU}},
  note         = {Machine review of arXiv:2411.16288}
}

read the original abstract

We survey results for Cameron-Liebler sets and low degree Boolean functions for Hamming graphs, Johnson graphs and Grassmann graphs from the point of view of association schemes. This survey covers selected results in finite geometry, Boolean function analysis, design theory, coding theory, and cryptography.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

111 extracted references · 78 canonical work pages

[1]

Abatangelo, G

V. Abatangelo, G. Korchmaros & B. Larato, Classification of maximal caps in PG(3, 5) different from elliptic quadrics , J. Geom. 57(1–2) (1996) 9–19

1996
[2]

N. Alon, I. Dinur, E. Friedgut & B. Sudakov, Graph Products, Fourier Analysis and Spectral Techniques, Geom. Funct. Anal. 14 (2004) 913–940

2004
[3]

R. A. Bailey, P. J. Cameron, A. L. Gavrilyuk & S. V. Goryainov, Equitable par- titions of Latin-square graphs , J. Combin. Des. 27(3) (2018) 142–160

2018
[4]

Bamberg & T

J. Bamberg & T. Penttila, Overgroups of Cyclic Sylow Subgroups of Linear Groups, Comm. Algebra 36(7) (2008) 2503–2543

2008
[5]

Bamberg, S

J. Bamberg, S. Kelly, M. Law & T. Penttila, Tight sets and m-ovoids of finite polar spaces, J. Combin. Theory Ser. A 114(7) (2007) 1293–1314

2007
[6]

Barak, Unique Games Conjecture – halfway there? , https://windowsontheory.org/2018/01/10/unique-games-conjecture-halfway-there/ , accessed: 31 October 2024

B. Barak, Unique Games Conjecture – halfway there? , https://windowsontheory.org/2018/01/10/unique-games-conjecture-halfway-there/ , accessed: 31 October 2024

2018
[7]

Barak, P

B. Barak, P. K. Kothari & D.Steurer, Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture , In 10th Innovations in Theoretical Computer Sci- ence Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum f¨ ur In- formatik (2019)

2019
[8]

Beutelspacher & U

A. Beutelspacher & U. Rosenbaum, Projective Geometry: From Foundations to Applications, Cambridge University Press, 1998

1998

Show all 111 references

[9]

R. E. Block, On the orbits of collineation groups , Math. Z. 96 (1967) 33–49

1967
[10]

Blokhuis, M

A. Blokhuis, M. De Boeck & J. D’haeseleer, Cameron-Liebler sets of k-spaces, Des. Codes Cryptogr. 87 (2019) 1839–1856

2019
[11]

A. E. Brouwer, S.M. Cioab˘ a, F. Ihringer & M. McGinnis, The smallest eigenval- ues of Hamming graphs, Johnson graphs and other distance-regular-graphs with classical parameters, J. Combin. Theory Ser. B 133 (2018), 88–121

2018
[12]

A. E. Brouwer, A. M. Cohen & A. Neumaier, Distance-regular graphs, Springer, Heidelberg, 1989

1989
[13]

A. E. Brouwer, C. D. Godsil, J. H. Koolen & W. J. Martin, Width and dual width of subsets in polynomial association schemes , J. Combin. Th. (A) 102(2) (2003) 255–271

2003
[14]

A. E. Brouwer and H. Van Maldeghem. Strongly Regular Graphs . Cambridge Univ. Press, 2022. 21

2022
[15]

A. A. Bruen & K. Drudge, The construction of Cameron-Liebler line classes in PG(3, q), Finite Fields Appl. 5(1) (1999) 35–45

1999
[16]

Calderbank & W

R. Calderbank & W. M. Kantor, The Geometry of Two-Weight Codes , Bull. London Math. Soc. 18 (1986) 97–122

1986
[17]

P. J. Cameron & R. A. Liebler, Tactical decompositions and orbits of projective groups, Linear Algebra Appl. 46 (1982) 91–102

1982
[18]

Camion, C

P. Camion, C. Carlet, P. Charpin & N. Sendrier, On Correlation-immune func- tions, In: Feigenbaum, J. (eds), Advances in Cryptology – CRYPTO ’91. CRYPTO 1991. Lecture Notes in Comput. Sci., vol 576. Springer, Berlin, Heidel- berg

1991
[19]

Chiarelli, P

J. Chiarelli, P. Hatami & M. Saks, An Asymptotically Tight Bound on the Num- ber of Relevant Variables in a Bounded Degree Boolean Function , Combinatorica 40(2) (2020) 237–244

2020
[20]

Cossidente & F

A. Cossidente & F. Pavese, Intriguing sets of quadrics in PG(5, q), Adv. Geom. 17 (2017) 339–345

2017
[21]

Cossidente & F

A. Cossidente & F. Pavese, New Cameron-Liebler line-classes with parameter q2+1 2 , J. Algebr. Comb. 49 (2018) 193–208

2018
[22]

Cossidente & F

A. Cossidente & F. Pavese, Cameron-Liebler line classes of PG(3, q) admitting P GL(2, q), J. Combin. Theory Ser. A 167 (2019) 104–120

2019
[23]

Dafni, Y

N. Dafni, Y. Filmus, N. Lifshitz, N. Lindzey & M. Vinyals, Complexity mea- sures on symmetric group and beyond , 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), 2021

2021
[24]

Damasco & D

J.R.C. Damasco & D. Frettl¨ oh, Perfect colourings of regular graphs , Contemp. Math. 764 (2021) 43–56

2021
[25]

De Beule, J

J. De Beule, J. Demeyer, K. Metsch & M. Rodgers, A new family of tight sets in Q+(5, q), Des. Codes Cryptogr. 78(3) (2016) 655–678

2016
[26]

De Beule & J

J. De Beule & J. Mannaert, A modular equality for Cameron-Liebler line classes in projective and affine spaces of odd dimension , Finite Fields Appl. 82 (2022) 102047

2022
[27]

De Beule, J

J. De Beule, J. Mannaert & L. Storme, Cameron-Liebler k-sets in subspaces and non-existence conditions, Des. Codes Cryptogr. 90 (2022) 633–651

2022
[28]

De Beule, J

J. De Beule, J. D’haeseleer, F. Ihringer & J. Mannaert, Degree 2 Boolean Func- tions on Grassmann Graphs , Electron. J. Combin. 30(1) (2023) P1.31

2023
[29]

De Beule, J

J. De Beule, J. Mannaert & L. Storme, On two non-existence results for Cameron- Liebler k-sets in PG(n, q), arXiv:2403.00519 [math.CO] (2024)

2024 arXiv
[30]

De Boeck & J

M. De Boeck & J. D’haeseleer, Equivalent definitions for (degree one) Cameron–Liebler classes of generators in finite classical polar spaces , Disc. Math. 343(1) (2020) 111642

2020
[31]

De Boeck, L

M. De Boeck, L. Storme & A. Svob, The Cameron–Liebler problem for sets, Disc. Math. 339(2) (2016) 470–474

2016
[32]

Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips research reports: Supplements

P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips research reports: Supplements. N.V. Philips’ Gloeilampenfabrieken, 1973

1973
[33]

Delsarte, Association schemes and t-designs in regular semilattices, J

P. Delsarte, Association schemes and t-designs in regular semilattices, J. Combin. Th. (A) 20 (1976) 230–243

1976
[34]

D’haeseleer, F

J. D’haeseleer, F. Ihringer, J. Mannaert & L. Storme, Cameron-Liebler k-sets in AG(n, q), Electron. J. Combin. 28(4) (2021) P4.11

2021
[35]

D’haeseleer, K

J. D’haeseleer, K. Meagher & V. R. T. Pantangi, Cameron–Liebler sets in per- mutation groups, Algebr. Comb. 7(4) (2024) 1157–1182. 22

2024
[36]

D’haeseleer, J

J. D’haeseleer, J. Mannaert, L. Storme & A. ˇSvob, Cameron-Liebler line classes in AG(3, q), Finite Fields Appl. 67 (2020) 101706

2020
[37]

Dinur, Y

I. Dinur, Y. Filmus & P. Harsha, Sparse juntas on the biased hypercube , Theoret- iCS 3 (2024)

2024
[38]

Dinur & E

I. Dinur & E. Friedgut, Intersecting families are essentially contained in juntas , Combin. Probab. Comput. 18(1–2) (2009) 107–122

2009
[39]

K. W. Drudge, Extremal sets in projective and polar spaces , PhD thesis, The University of Western Ontario, 1998

1998
[40]

Ellis, E

D. Ellis, E. Friedgut & H. Pilpel, Intersecting families of permutations , J. Amer. Math. Soc. 24 (2011) 649–682

2011
[41]

Ellis, Y

D. Ellis, Y. Filmus & E. Friedgut, A quasi-stability result for dictatorships in Sn, Combinatorica 35(5) (2015) 573–618

2015
[42]

Ellis, Y

D. Ellis, Y. Filmus & E. Friedgut, A stability result for balanced dictatorships in Sn, Random Structures Algorithms 46(3) (2015) 494–530

2015
[43]

Ellis, G

D. Ellis, G. Kindler & N. Lifshitz, An analogue of Bonami’s Lemma for functions on spaces of linear maps, and 2-2 Games, arXiv:2209.04243v1 [math.CO] (2022)

2022
[44]

Erd˝ os, C

P. Erd˝ os, C. Ko & R. Rado,Intersection theorems for finite sets , Quart. J. Math. Oxford Ser. (2) 12 (1961) 313–320

1961
[45]

R. J. Evans, A. L. Gavrilyuk, S. Goryainov & K. Vorob’ev, Equitable 2-partitions of the Johnson graphs J(n, 3), arXiv:2206.15341 [math.CO], 2022

2022 arXiv
[46]

S. Evra, G. Kindler & N. Lifshitz, Polynomial Bogolyubov for special linear groups via tensor rank , arXiv:2404.00641v1 [math.CO] (2024)

2024 arXiv
[47]

T. Feng, K. Momihara, M. Rodgers, Q. Xiang & H. Zou, Cameron-Liebler line classes with parameter x = (q+1)2 3 , Adv. Math. 385 (2021) 107780

2021
[48]

T. Feng, K. Momihara & Q. Xiang, Cameron-Liebler line classes with parameter x = q2−1 2 , J. Combin. Theory Ser. A 133 (2015) 307–338

2015
[49]

Filmus, Friedgut–Kalai–Naor theorem for slices of the Boolean cube , Chic

Y. Filmus, Friedgut–Kalai–Naor theorem for slices of the Boolean cube , Chic. J. Theoret. Comput. Sci. (2016) 14:1–14:17

2016
[50]

Filmus, Orthogonal basis for functions over a slice of the Boolean hypercube , Electron

Y. Filmus, Orthogonal basis for functions over a slice of the Boolean hypercube , Electron. J. Combin. 23(1) (2016) P1.23

2016
[51]

Filmus, Boolean functions on Sn which are nearly linear, Discrete Anal

Y. Filmus, Boolean functions on Sn which are nearly linear, Discrete Anal. (2021) 25:1–25:27

2021
[52]

Filmus, FKN theorems for the biased cube and the slice , Manuscript (2021) https://yuvalfilmus.cs.technion.ac.il/Papers/FKN-Exposition.pdf

Y. Filmus, FKN theorems for the biased cube and the slice , Manuscript (2021) https://yuvalfilmus.cs.technion.ac.il/Papers/FKN-Exposition.pdf

2021
[53]

Filmus, Junta Threshold for Low Degree Boolean Functions on the Slice , Elec- tron

Y. Filmus, Junta Threshold for Low Degree Boolean Functions on the Slice , Elec- tron. J. Combin. 30(1) (2023) P1.55

2023
[54]

Filmus & F

Y. Filmus & F. Ihringer, Boolean degree 1 functions on some classical association schemes, J. Combin. Theory Ser. A 162 (2019) 241–270

2019
[55]

Filmus & F

Y. Filmus & F. Ihringer, Boolean constant degree functions on the slice are juntas, Disc. Math. 342(12) (2019) 111614

2019
[56]

Filmus & N

Y. Filmus & N. Lindzey, Murali’s basis for the slice , https://yuvalfilmus.cs. technion.ac.il/Manuscripts/Murali.pdf, 2020, accessed: 27 Oct 2024

2020
[57]

Filmus & A

Y. Filmus & A. Vinciguerra, On the restriction threshold for Boolean functions on the slice , Unpublished Note, 2023

2023
[58]

Frankl & R

P. Frankl & R. M. Wilson, The Erd˝ os-Ko-Rado theorem for vector spaces , J. Combin. Theory Ser. A 43(2) (1986) (228–236). 23

1986
[59]

Friedgut, On the measure of intersecting families, uniqueness and stability , Combinatorica 28(5) (2008) 503–508

E. Friedgut, On the measure of intersecting families, uniqueness and stability , Combinatorica 28(5) (2008) 503–508

2008
[60]

Friedgut, G

E. Friedgut, G. Kalai & A. Naor, Boolean functions whose Fourier transform is concentrated on the first two levels , Adv. Appl. Math. 29(3) (2002) 427–437

2002
[61]

A. L. Gavrilyuk & S. V. Goryainov, On perfect 2-colorings of Johnson graphs J(v, 3), J. Combin. Des. 21(6) (2013) 232–252

2013
[62]

Gavrilyuk, I

A. Gavrilyuk, I. Matkin & T. Penttila, Derivation of Cameron–Liebler line classes, Des. Codes Cryptogr. 86(1) (2018) 231–236

2018
[63]

A. L. Gavrilyuk & I. Matkin, Cameron-Liebler line classes in PG(3, 5), J. Combin. Des. 26(12) (2018) 563–580

2018
[64]

Gavrilyuk & K

A. Gavrilyuk & K. Metsch, A modular equality for Cameron-Liebler line classes , J. Comb. Theory A 127 (2014) 224–242

2014
[65]

A. L. Gavrilyuk & I. Yu. Mogilnykh, Cameron-Liebler line classes in PG(n, 4), Des. Codes Cryptogr. 73(3) (2014) 969–982

2014
[66]

Gavrilyuk & V

A. Gavrilyuk & V. A. Zinoviev, Completely Regular Codes in the Johnson Graph , In: Completely Regular Codes in Distance Regular Graphs, CRC Press, 2025

2025
[67]

Godsil & K

C. Godsil & K. Meagher, Erd˝ os-Ko-Rado Theorems: Algebraic Approaches, Cam- bridge studies in advances mathematics, Cambridge University Press, 2016

2016
[68]

Golubev, Graphical designs and extremal combinatorics, Linear Algebra Appl

K. Golubev, Graphical designs and extremal combinatorics, Linear Algebra Appl. 604 (2020) 490–506

2020
[69]

Govaerts & T

P. Govaerts & T. Penttila, Cameron-Liebler line classes in PG(3, 4), Bull. Belg. Math. Soc. Simon Stevin 12(5) (2005) 793–804

2005
[70]

Graham, K

R. Graham, K. Leeb & B. Rothschild, Ramsey’s theorem for a class of categories , Adv. Math. 8 (1972) 417–433

1972
[71]

Guo, Cameron–Liebler sets in bilinear forms graphs , Des

J. Guo, Cameron–Liebler sets in bilinear forms graphs , Des. Codes Cryptogr. 89 (2021) 1159–1180

2021
[72]

W. H. Haemers, Interlacing eigenvalues and graphs , Linear Algebra Appl. 226– 228 (1995) 593–616

1995
[73]

Ihringer, The classification of Boolean degree functions in high-dimensional finite vector spaces, Proc

F. Ihringer, The classification of Boolean degree functions in high-dimensional finite vector spaces, Proc. Amer. Math. Soc. 152(12) (2024) 5355–5365

2024
[74]

Ihringer, The Chromatic Number of the q-Kneser Graph for Large q, Elec- tron

F. Ihringer, The Chromatic Number of the q-Kneser Graph for Large q, Elec- tron. J. Combin. 26(1) (2019) P1.50

2019
[75]

Ihringer, Remarks on the Erd˝ os Matching Conjecture for vector spaces , Eu- rop

F. Ihringer, Remarks on the Erd˝ os Matching Conjecture for vector spaces , Eu- rop. J. Combinatorics 94 (2021) 103306

2021
[76]

Ito, Designs in a coset geometry: Delsarte theory revisited , Europ

T. Ito, Designs in a coset geometry: Delsarte theory revisited , Europ. J. Combi- natorics 25(2) (2004) 229–238

2004
[77]

W. M. Kantor, On Incidence Matrices of Finite Projective and Affine Spaces , Math. Z. 124 (1972) 315–318

1972
[78]

Keller & O

N. Keller & O. Klein, A structure theorem for almost low-degree functions on the slice, Israel J. Math. 240 (2020) 179–221

2020
[79]

S. Khot, D. Minzer & M. Safra, Pseudorandom sets in Grassmann graph have near-perfect expansion, Ann. of Math. (2) 198 (2023) 1–92

2023
[80]

Kiermaier, J

M. Kiermaier, J. Mannaert & A. Wassermann, The degree of functions in the Johnson and q-Johnson schemes , arXiv:2405.07572v1 [math.CO] (2024)

2024
[81]

Kindler & S

G. Kindler & S. Safra, Noise-resistant Boolean functions are juntas , Manuscript, 2002 24

2002
[82]

Kaufman & D

T. Kaufman & D. Minzer, Improved Optimal Testing Results from Global Hyper- contractivity, arXiv:2202.08688v1 [cs.CC] (2022)

2022 arXiv
[83]

D. S. Krotov & A. A. Valyuzhenich, On degree-3 and (n − 4)-correlation-immune perfect colorings of n-cubes, Discrete Math. 347 (2024) 114138

2024
[84]

Lov´ asz, On the Shannon capacity of a graph , IEEE Trans

L. Lov´ asz, On the Shannon capacity of a graph , IEEE Trans. Inform. Theory 25(1) (1979) 1–7

1979
[85]

W. J. Martin, Completely Regular Designs of Strength One , J. Algebraic Combin. 3(2) (1994) 177–185

1994
[86]

Matkin, Cameron-Liebler line classes in P G(n, 5), Trudy Inst

I. Matkin, Cameron-Liebler line classes in P G(n, 5), Trudy Inst. Mat. i Mekh. UrO RAN 24(2) (2018) 158–172

2018
[87]

Metsch, The non-existence of Cameron-Liebler line classes with parameter 2 < x≤ q, Bull

K. Metsch, The non-existence of Cameron-Liebler line classes with parameter 2 < x≤ q, Bull. Lond. Math. Soc 6 (2010) 991–996

2010
[88]

Metsch, An improved bound on the existence of Cameron-Liebler line classes , J

K. Metsch, An improved bound on the existence of Cameron-Liebler line classes , J. Comb. Theory A 121 (2014) 89–93

2014
[89]

Metsch, A gap result for Cameron-Liebler k-classes, Discrete Math

K. Metsch, A gap result for Cameron-Liebler k-classes, Discrete Math. 340(6) (2017) 1311–1318

2017
[90]

A. D. Meyerowitz, Cycle-balanced partitions in distance-regular graphs, J. Combin. Inform. System Sci. 17(1–2) (1992) 39–42

1992
[91]

Minzer & K

D. Minzer & K. Zheng, Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries, arXiv:2304.05598v1 [cs.CC] (2023)

2023 arXiv
[92]

Nisan & M

N. Nisan & M. Szegedy, On the degree of Boolean functions as real polynomials , Comput. Complexity 4(4) (1994) 301–313

1994
[93]

O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014

R. O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014

2014
[94]

Rodgers, On Some New Examples of Cameron–Liebler Line Classes , PhD thesis, University of Colorado, Denver (2012)

M. Rodgers, On Some New Examples of Cameron–Liebler Line Classes , PhD thesis, University of Colorado, Denver (2012)

2012
[95]

Rodgers, L

M. Rodgers, L. Storme & A. Vansweevelt, Cameron-Liebler k-classes in PG(2k + 1, q), Combinatorica 38(3) (2018) 739–757

2018
[96]

Roos, On antidesigns and designs in association schemes , Delft Progress Re- port 7(2) (1982) 98–109

C. Roos, On antidesigns and designs in association schemes , Delft Progress Re- port 7(2) (1982) 98–109

1982
[97]

M. K. Srinivasan, Symmetric chains, Gelfand–Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme , J. Algebraic Combin. 34 (2011) 301–322

2011
[98]

Steinerberger, Generalized designs on graphs: Sampling, spectra, symmetries , J

S. Steinerberger, Generalized designs on graphs: Sampling, spectra, symmetries , J. Graph Theory 93(2) (2020) 253–267

2020
[99]

Tallini Scafati, Calotte di tipo (m, n) in uno spazio di Galois Sr,q, Atti Accad

M. Tallini Scafati, Calotte di tipo (m, n) in uno spazio di Galois Sr,q, Atti Accad. Peloritana Pericolanti Cl. Sci. Fis. Mat. Natur., Rendiconti, Serie 8 (53)(1–2) (1972) 71–81

1972
[100]

Tallini Scafati, Sui k—insiemi di uno spazio di Galois Sr,q a due soli caratteri nella dimensione d, Atti Accad

M. Tallini Scafati, Sui k—insiemi di uno spazio di Galois Sr,q a due soli caratteri nella dimensione d, Atti Accad. Peloritana Pericolanti Cl. Sci. Fis. Mat. Natur., Rendiconti, Serie 8 60(6) (1976) 782–788

1976
[101]

Tanaka & N

H. Tanaka & N. Tokushige, Extremal problems for intersecting families of sub- spaces with a measure , arXiv:2404.17385v1 [math.CO] (2024)

2024 arXiv
[102]

Tarannikov, On resilient Boolean functions with maximal possible nonlinear- ity, Proc

Y. Tarannikov, On resilient Boolean functions with maximal possible nonlinear- ity, Proc. of Indocrypt’2000, Lecture Notes in Computer Science 1977 (2000), 19–30

2000
[103]

Synthesis and complex- ity of controlling systems

Y. V. Tarannikov & D. P. Kirienko, Spectral Analysis of High Order Correlation Immune Function, Proc. of international school-seminar “Synthesis and complex- ity of controlling systems”, Moscow, 2001. 25

2001
[104]

Tarannikov, P

Y. Tarannikov, P. Korolev & A. Botev, Autocorrelation Coefficients and Corre- lation Immunity of Boolean Functions , Advances in Cryptology — ASIACRYPT 2001, Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg

2001
[105]

D. E. Taylor, The Geometry of the Classical Groups , Heldermann, Berlin, 1992

1992
[106]

Valyuzhenich, An upper bound on the number of relevant variables for Boolean functions on the Hamming graph , arXiv:2404.10418v1 [math.CO] (2024)

A. Valyuzhenich, An upper bound on the number of relevant variables for Boolean functions on the Hamming graph , arXiv:2404.10418v1 [math.CO] (2024)

2024 arXiv
[107]

Vanhove, Incidence geometry from an algebraic graph theory point of view , PhD thesis, University of Ghent, 2011

F. Vanhove, Incidence geometry from an algebraic graph theory point of view , PhD thesis, University of Ghent, 2011

2011
[108]

Vorob’ev, Equitable 2-partitions of Johnson graphs with the second eigenvalue, https://arxiv.org/pdf/2003.10956 [math.CO] (2020)

K. Vorob’ev, Equitable 2-partitions of Johnson graphs with the second eigenvalue, https://arxiv.org/pdf/2003.10956 [math.CO] (2020)

2020 arXiv
[109]

Wellens, Relationships between the number of inputs and other complexity measures of Boolean functions , Discrete Anal

J. Wellens, Relationships between the number of inputs and other complexity measures of Boolean functions , Discrete Anal. 19 (2022)

2022
[110]

Zhu, Optimal and extremal graphical designs on regular graphs associated with classical parameters, Des

Y. Zhu, Optimal and extremal graphical designs on regular graphs associated with classical parameters, Des. Codes Cryptogr. 91(8) (2023) 2737–2754

2023
[111]

Zverev, On the Structure of the Spectrum Support of Boolean Functions, Boolean Functions, In: Cryptology and Information Security, NATO Sci

A. Zverev, On the Structure of the Spectrum Support of Boolean Functions, Boolean Functions, In: Cryptology and Information Security, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., Volume 18, 2008. 26

2008

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Abatangelo, G

V. Abatangelo, G. Korchmaros & B. Larato, Classification of maximal caps in PG(3, 5) different from elliptic quadrics , J. Geom. 57(1–2) (1996) 9–19

1996

[2] [2]

N. Alon, I. Dinur, E. Friedgut & B. Sudakov, Graph Products, Fourier Analysis and Spectral Techniques, Geom. Funct. Anal. 14 (2004) 913–940

2004

[3] [3]

R. A. Bailey, P. J. Cameron, A. L. Gavrilyuk & S. V. Goryainov, Equitable par- titions of Latin-square graphs , J. Combin. Des. 27(3) (2018) 142–160

2018

[4] [4]

Bamberg & T

J. Bamberg & T. Penttila, Overgroups of Cyclic Sylow Subgroups of Linear Groups, Comm. Algebra 36(7) (2008) 2503–2543

2008

[5] [5]

Bamberg, S

J. Bamberg, S. Kelly, M. Law & T. Penttila, Tight sets and m-ovoids of finite polar spaces, J. Combin. Theory Ser. A 114(7) (2007) 1293–1314

2007

[6] [6]

Barak, Unique Games Conjecture – halfway there? , https://windowsontheory.org/2018/01/10/unique-games-conjecture-halfway-there/ , accessed: 31 October 2024

B. Barak, Unique Games Conjecture – halfway there? , https://windowsontheory.org/2018/01/10/unique-games-conjecture-halfway-there/ , accessed: 31 October 2024

2018

[7] [7]

Barak, P

B. Barak, P. K. Kothari & D.Steurer, Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture , In 10th Innovations in Theoretical Computer Sci- ence Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum f¨ ur In- formatik (2019)

2019

[8] [8]

Beutelspacher & U

A. Beutelspacher & U. Rosenbaum, Projective Geometry: From Foundations to Applications, Cambridge University Press, 1998

1998