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) Extremal set theory (05D05) Association schemes, strongly regular graphs (05E30) Semidefinite programming (90C22) Combinatorial optimization (90C27)

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

• 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
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Independent sets in association schemes
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• 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 eigenvalue method for cross t-intersecting families
• The Erdős-Ko-Rado theorem for twisted Grassmann graphs
• The Erdős-Ko-Rado theorem for vector spaces
• 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

(13)

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

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)