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

DOI10.1112/BLMS/BDT101zbMATH Open1285.05181arXiv1304.5466OpenAlexW3099904847MaRDI QIDQ5409116FDOQ5409116

Authors: Sho Suda, Hajime Tanaka 

Publication date: 14 April 2014

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

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.

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

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)\)

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)

Cites Work

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

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)