Large \0,1,,t\-cliques in dual polar graphs

DOI10.1016/J.JCTA.2017.08.018MaRDI QIDQ1679332zbMATH OpenOpenAlexFDO

Authors Ferdinand Ihringer, Klaus Metsch

Publication date 9 November 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.01697

zbMATH Keywords

distance-regular graphErdős-Ko-Rado theoremindependent setpolar space

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We investigate $0,1,ldots,t$-cliques of generators on dual polar graphs of finite classical polar spaces of rank $d$. These cliques are also known as ErdH{o}s-Ko-Rado sets in polar spaces of generators with pairwise intersections in at most codimension $t$. Our main result is that we classify all such cliques of maximum size for $tleqsqrt8d/5-2$ if $qgeq3$, and $tleqsqrt8d/9-2$ if $q=2$. We have the following byproducts. (a) For $qgeq3$ we provide estimates of Hoffman's bound on these $0,1,ldots,t$-cliques for all $t$. (b) For $qgeq3$ we determine the largest, second largest, and smallest eigenvalue of the graphs which have the generators of a polar space as vertices and where two generators are adjacent if and only if they meet in codimension at least $t+1$. Furthermore, we provide nice explicit formulas for all eigenvalues of these graphs. (c) We provide upper bounds on the size of the second largest maximal $0,1,ldots,t$-cliques for some $t$.

Recommendations

• On maximal cliques of polar graphs
• A note on Erdős-Ko-Rado sets of generators in Hermitian polar spaces
• On the maximum size of Erdős-Ko-Rado sets in \(H(2d+1, q^2)\)
• On the large maximal \(\{ 0,1,2,\dots,t\}\)-cliques in Hamming graph \(H(n,q)\)
• scientific article; zbMATH DE number 4132192

Cites work

• A Hilton-Milner theorem for vector spaces
• A new family of distance-regular graphs and the \(\{ 0,1,2 \}\)-cliques in dual polar graphs
• A note on Erdős-Ko-Rado sets of generators in Hermitian polar spaces
• Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs
• Erdős-Ko-Rado theorems for permutations and set partitions
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 53569 (Why is no real title available?)
• scientific article; zbMATH DE number 1101474 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems for systems of finite vector spaces
• On the maximum size of Erdős-Ko-Rado sets in \(H(2d+1, q^2)\)
• Some Erdös–Ko–Rado Theorems for Chevalley Groups
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Some q-Krawtchouk Polynomials on Chevalley Groups
• The complete intersection theorem for systems of finite sets
• The eigenspaces of the Bose-Mesner algebras of the association schemes corresponding to projective spaces and polar spaces
• The Erdős-Ko-Rado theorem for vector spaces
• The exact bound in the Erdős-Ko-Rado theorem
• The largest Erdős-Ko-Rado sets of planes in finite projective and finite classical polar spaces
• The second largest Erdős-Ko-Rado sets of generators of the hyperbolic quadrics \(\mathcal{Q}^+(4n + 1, q)\)
• Theorems of Erdős-Ko-Rado type in polar spaces

Cited in

(10)

• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs
• On maximal cliques of polar graphs
• Large maximal \(\{ 0,1,2,\dots,t\}\)-cliques of the \(q\)-analog of the Johnson graph
• Remarks on the Erdős matching conjecture for vector spaces
• Non-trivial t-intersecting families for symplectic polar spaces
• A note on Erdős-Ko-Rado sets of generators in Hermitian polar spaces
• On the chromatic number of some generalized Kneser graphs
• On the treewidth of generalized q-Kneser graphs
• Graphes liés aux espaces polaires

This page was built for publication: Large \(\{0,1,\ldots,t\}\)-cliques in dual polar graphs

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