×

zbMATH — the first resource for mathematics

Boolean degree 1 functions on some classical association schemes. (English) Zbl 1401.05317
Summary: We investigate Boolean degree 1 functions for several classical association schemes, including Johnson graphs, Grassmann graphs, graphs from polar spaces, and bilinear forms graphs, as well as some other domains such as multislices (Young subgroups of the symmetric group). In some settings, Boolean degree 1 functions are also known as completely regular strength 0 codes of covering radius 1, Cameron-Liebler line classes, and tight sets.
We classify all Boolean degree 1 functions on the multislice. On the Grassmann scheme \(J_q(n, k)\) we show that all Boolean degree 1 functions are trivial for \(n \geq 5\), \(k\), \(n - k \geq 2\) and \(q \in \{2, 3, 4, 5 \}\), and that, for general \(q\), the problem can be reduced to classifying all Boolean degree 1 functions on \(J_q(n, 2)\). We also consider polar spaces and the bilinear forms graphs, giving evidence that all Boolean degree 1 functions are trivial for appropriate choices of the parameters.

MSC:
05E30 Association schemes, strongly regular graphs
PDF BibTeX XML Cite
Full Text: DOI arXiv Link
References:
[1] Alon, Noga; Dinur, Irit; Friedgut, Ehud; Sudakov, Benny, Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal., 14, 5, 913-940, (2004) · Zbl 1056.05104
[2] Bamberg, John; Kelly, Shane; Law, Maska; Penttila, Tim, Tight sets and m-ovoids of finite polar spaces, J. Combin. Theory Ser. A, 114, 7, 1293-1314, (2007) · Zbl 1124.51003
[3] Brouwer, Andries E.; Cioabă, Sebastian M.; Ihringer, Ferdinand; McGinnis, Matt, The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters, J. Combin. Theory Ser. B, 133, 88-121, (2018) · Zbl 1397.05098
[4] Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold, Distance-Regular Graphs, Ergeb. Math. Grenzgeb. (3), vol. 3, (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[5] Brouwer, Andries E.; Godsil, Chris D.; Koolen, Jack H.; Martin, William J., Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A, 102, 2, 255-271, (2003) · Zbl 1018.05108
[6] Bruen, Aiden A.; Drudge, Keldon, The construction of Cameron-Liebler line classes in \(\operatorname{PG}(3, q)\), Finite Fields Appl., 5, 1, 35-45, (1999) · Zbl 0927.51012
[7] Cameron, Peter J.; Liebler, Robert A., Tactical decompositions and orbits of projective groups, Linear Algebra Appl., 46, 91-102, (1982) · Zbl 0504.05015
[8] Cossidente, Antonio; Pavese, Francesco, New Cameron-Liebler line classes with parameter \(\frac{q^2 + 1}{2}\), J. Algebraic Combin., (2018)
[9] De Beule, Jan; Demeyer, Jeroen; Metsch, Klaus; Rodgers, Morgan, A new family of tight sets in \(Q^+(5, q)\), Des. Codes Cryptogr., 78, 3, 655-678, (2016) · Zbl 1336.51002
[10] De Boeck, Maarten; Rodgers, Morgan; Storme, Leo; Svob, Andrea, Cameron-Liebler sets of generators in finite classical polar spaces, (2017)
[11] De Boeck, Maarten; Storme, Leo; Svob, Andrea, The Cameron-Liebler problem for sets, Discrete Math., 339, 2, 470-474, (2016) · Zbl 1327.05326
[12] De Bruyn, Bart; Suzuki, Hiroshi, Intriguing sets of vertices of regular graphs, Graphs Combin., 26, 5, 629-646, (2010) · Zbl 1230.05297
[13] Delsarte, Philippe, An algebraic approach to the association schemes of coding theory, Philips Res. Rep., Suppl., 10, (1973), vi+97 · Zbl 1075.05606
[14] Delsarte, Philippe, Bilinear forms over a finite field with applications to coding theory, J. Combin. Theory Ser. A, 25, 226-241, (1978) · Zbl 0397.94012
[15] Dennis, Stanton, Some q-Krawtchouk polynomials on Chevalley groups, Amer. J. Math., 102, 4, 625-662, (1980) · Zbl 0448.33019
[16] Dinur, Irit; Khot, Subhash; Kindler, Guy; Minzer, Dor; Safra, Muli, Towards a Proof of the 2-to-1 Games Conjecture?, (2016), ECCC, Technical Report TR16-198
[17] Dinur, Irit; Khot, Subhash; Kindler, Guy; Minzer, Dor; Safra, Muli, On Non-Optimally Expanding Sets in Grassmann Graphs, (2017), ECCC, Technical Report TR17-094 · Zbl 1370.68130
[18] Drudge, Keldon W., Extremal Sets in Projective and Polar Spaces, (1998), The University of Western: The University of Western Ontario, PhD thesis
[19] Eisfeld, Jörg, Subsets of association schemes corresponding to eigenvectors of the Bose-Mesner algebra, Finite Geometry and Combinatorics, Deinze, 1997, Bull. Belg. Math. Soc. Simon Stevin, 5, 2-3, 265-274, (1998) · Zbl 0939.51010
[20] Eisfeld, Jörg, The eigenspaces of the Bose-Mesner algebras of the association schemes corresponding to projective spaces and polar spaces, Des. Codes Cryptogr., 17, 1-3, 129-150, (1999) · Zbl 0970.51008
[21] Ellis, David; Filmus, Yuval; Friedgut, Ehud, A quasi-stability result for dictatorships in \(S_n\), Combinatorica, 35, 5, 573-618, (2015) · Zbl 1389.05167
[22] Ellis, David; Filmus, Yuval; Friedgut, Ehud, A stability result for balanced dictatorships in \(S_n\), Random Structures Algorithms, 46, 3, 494-530, (2015) · Zbl 1342.94135
[23] Ellis, David; Filmus, Yuval; Friedgut, Ehud, Low-degree Boolean functions on \(S_n\), with an application to isoperimetry, Forum Math. Sigma, 5, (2017) · Zbl 1384.05149
[24] Ellis, David; Friedgut, Ehud; Pilpel, Haran, Intersecting families of permutations, J. Amer. Math. Soc., 24, 649-682, (2011) · Zbl 1285.05171
[25] Feng, Tao; Momihara, Koji; Xiang, Qing, Cameron-Liebler line classes with parameter \(x = \frac{q^2 - 1}{2}\), J. Combin. Theory Ser. A, 133, 307-338, (2015) · Zbl 1352.05195
[26] Filmus, Yuval, Friedgut-Kalai-Naor theorem for slices of the Boolean cube, Chic. J. Theoret. Comput. Sci., (2016), 17 pp · Zbl 1401.06014
[27] Filmus, Yuval, Orthogonal basis for functions over a slice of the Boolean hypercube, Electron. J. Combin., 23, 1, 1.23, (2016) · Zbl 1330.05163
[28] Filmus, Yuval, A comment on intersecting families of permutations, CoRR, abs/1706.10146, (2017)
[29] Filmus, Yuval; Ihringer, Ferdinand, Boolean constant degree functions on the slice are juntas, CoRR, abs/1801.06338, (2018)
[30] Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl, Invariance principle on the slice, (31st Computational Complexity Conference, (2016)) · Zbl 1380.60020
[31] Filmus, Yuval; Mossel, Elchanan, Harmonicity and invariance on slices of the Boolean cube, (31st Computational Complexity Conference, (2016)) · Zbl 1380.60021
[32] Friedgut, Ehud; Kalai, Gil; Naor, Assaf, Boolean functions whose Fourier transform is concentrated on the first two levels, Adv. in Appl. Math., 29, 3, 427-437, (2002) · Zbl 1039.91014
[33] Gavrilyuk, Alexander L.; Matkin, I., Cameron-liebler line classes in \(P G(3, 5)\), J. Combin. Des., 26, 12, 563-580, (2018)
[34] Gavrilyuk, Alexander L.; Matkin, Ilia; Penttila, Tim, Derivation of Cameron-Liebler line classes, Des. Codes Cryptogr., 86, 231-236, (2018) · Zbl 1393.51003
[35] Gavrilyuk, Alexander L.; Metsch, Klaus, A modular equality for Cameron-Liebler line classes, J. Combin. Theory Ser. A, 127, 224-242, (2014) · Zbl 1302.51008
[36] Gavrilyuk, Alexander L.; Mogilnykh, Ivan Yu., Cameron-Liebler line classes in \(P G(n, 4)\), Des. Codes Cryptogr., 73, 3, 969-982, (2014) · Zbl 1305.51008
[37] Godsil, Chris; Meagher, Karen, Erdős-Ko-Rado Theorems: Algebraic Approaches, Cambridge Stud. Adv. Math., vol. 149, (December 2016), Cambridge Univ. Press
[38] Govaerts, Patrick; Penttila, Tim, Cameron-Liebler line classes in \(\operatorname{PG}(3, 4)\), Bull. Belg. Math. Soc. Simon Stevin, 12, 5, 793-804, (2005) · Zbl 1142.51005
[39] Guy Kindler, Shmuel Safra, Noise-resistant Boolean functions are juntas, manuscript. · Zbl 1076.68112
[40] Hua, Loo-Keng, Geometry of symmetric matrices over any field with characteristic other than two, Ann. of Math. (2), 50, 8-31, (1949) · Zbl 0034.15701
[41] Khot, Subhash; Minzer, Dor; Safra, Muli, On independent sets, 2-to-2 games, and Grassmann graphs, (Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, (2017), ACM: ACM New York, NY, USA), 576-589 · Zbl 1370.68130
[42] Khot, Subhash; Minzer, Dor; Safra, Muli, Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion, (2018), ECCC, Technical Report TR18-006 · Zbl 1370.68130
[43] Kindler, Guy, Property Testing, PCP and Juntas, (2002), Tel-Aviv University, PhD thesis
[44] Martin, William J., Completely regular designs of strength one, J. Algebraic Combin., 3, 2, 177-185, (1994) · Zbl 0799.05012
[45] Matkin, I., Cameron-Liebler line classes in \(P G(n, 5)\), Trudy Inst. Mat. i Mekh. UrO RAN, 24, 2, 158-172, (2018)
[46] Meagher, Karen; Spiga, Pablo; Tiep, Pham Huu, An Erdős-Ko-Rado theorem for finite 2-transitive groups, European J. Combin., 550, 100-118, (2016) · Zbl 1333.05306
[47] Metsch, Klaus, An improved bound on the existence of Cameron-Liebler line classes, J. Combin. Theory Ser. A, 121, 89-93, (2014) · Zbl 1284.51008
[48] Metsch, Klaus, A gap result for Cameron-Liebler k-classes, Discrete Math., 340, 6, 1311-1318, (2017) · Zbl 1375.51006
[49] Meyerowitz, Aaron D., Cycle-balanced partitions in distance-regular graphs, J. Comb. Inf. Syst. Sci., 17, 1-2, 39-42, (1992) · Zbl 1231.05303
[50] Nathan Keller, Ohad Klein, Kindler-Safra theorem for the slice, 2017, manuscript.
[51] O’Donnell, Ryan, Analysis of Boolean Functions, (2014), Cambridge University Press · Zbl 1336.94096
[52] O’Donnell, Ryan; Wimmer, Karl, KKL, Kruskal-Katona, and monotone nets, SIAM J. Comput., 42, 6, 2375-2399, (2013) · Zbl 1285.68075
[53] Pentilla, Tim, Collineations and Configurations in Projective Spaces, (1985), Oxford University, PhD thesis
[54] Penttila, Tim, Cameron-Liebler line classes in \(\operatorname{PG}(3, q)\), Geom. Dedicata, 37, 3, 245-252, (1991) · Zbl 0724.51017
[55] Rodgers, Morgan; Storme, Leo; Vansweevelt, Andries, The Cameron-Liebler k-classes in \(p g(2 k + 1, q)\), Combinatorica, (2018)
[56] Schmidt, Kai-Uwe, Hermitian rank distance codes, Des. Codes Cryptogr., (2018) · Zbl 1401.94219
[57] Terwilliger, Paul, Quantum matroids, (Bannai, E.; Munemasa, A., Progress in Algebraic Combinatorics, Adv. Stud. Pure Math., vol. 24, (1996), Mathematical Society of Japan: Mathematical Society of Japan Tokyo), 323-441 · Zbl 0855.06004
[58] Tits, Jacques, Buildings of Spherical Type and Finite BN-Pairs, Lecture Notes in Math., vol. 386, (1974), Springer-Verlag: Springer-Verlag Berlin · Zbl 0295.20047
[59] Vanhove, Frédéric, Incidence Geometry from an Algebraic Graph Theory Point of View, (2011), Ghent University, PhD thesis · Zbl 1226.05076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.