A cross-intersection theorem for vector spaces based on semidefinite programming

DOI10.1112/BLMS/BDT101MaRDI QIDQ5409116zbMATH OpenOpenAlexFDO

Authors Sho Suda, Hajime Tanaka

Publication date 14 April 2014

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Lovász's theta functionoptimal feasible solutions to a semidefinite programming problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial optimization (90C27) Semidefinite programming (90C22) Association schemes, strongly regular graphs (05E30) Extremal set theory (05D05)

Abstract: Let $mathscrF$ and $mathscrG$ be families of $k$- and $ell$-dimensional subspaces, respectively, of a given $n$-dimensional vector space over a finite field $mathbb{F}_q$. Suppose that $xcapye0$ for all $xinmathscrF$ and $yinmathscrG$. By explicitly constructing optimal feasible solutions to a semidefinite programming problem which is akin to Lov'{a}sz's theta function, we show that $$, provided that $ngeq2k$ and $ngeq2ell$. The characterization of the extremal families is also established.

Recommendations

• A semidefinite programming approach to a cross-intersection problem with measures
• Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
• \(r\)-cross \(t\)-intersecting families for vector spaces
• Intersection theorems for vector spaces
• Non \(t\)-intersecting families of linear spaces over \(GF(q)\)

Cites work

• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• A comparison of the Delsarte and Lovász bounds
• A new generalization of the Erdős-Ko-Rado theorem
• Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs
• Coherent algebras
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Independent sets in association schemes
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• On the Shannon capacity of a graph
• Shadows and intersections in vector spaces
• The Erdős-Ko-Rado theorem for twisted Grassmann graphs
• The Erdős-Ko-Rado theorem for vector spaces
• The eigenvalue method for cross t-intersecting families
• The exact bound in the Erdős-Ko-Rado theorem
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• The subconstituent algebra of an association scheme. I

Cited in

(11)

• Refuting conjectures in extremal combinatorics via linear programming
• The proportion of non-degenerate complementary subspaces in classical spaces
• The maximum product of weights of cross-intersecting families
• r$r$‐Cross t$t$‐intersecting families via necessary intersection points
• A semidefinite programming approach to a cross-intersection problem with measures
• An Erdős-Ko-Rado theorem for cross t-intersecting families
• A cross‐intersection theorem for subsets of a set
• \(r\)-cross \(t\)-intersecting families for vector spaces
• Invitation to intersection problems for finite sets
• Intersection theorems for vector spaces
• The maximum measure of non-trivial 3-wise intersecting families

This page was built for publication: A cross-intersection theorem for vector spaces based on semidefinite programming

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