2024/04/01 by Ishay Haviv, Sam Mattheus, Haviv, Ishay +5
Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2404.01057
openalex publication_date 2024/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
For a field \mathbbF and integers d and k, a set \cal A ⊆ \mathbbFd is called k-nearly orthogonal if its members are non-self-orthogonal and every k+1 vectors of \cal A include an orthogonal pair. We prove that for every prime p there exists some δ= δ(p)>0, such that for every field \mathbbF of characteristic p and for all integers k ≥ 2 and d ≥ k, there exists a k-nearly orthogonal set of at least dδ⋅ k/log k vectors of \mathbbFd. The size of the set is optimal up to the log k term in the exponent. We further prove two extensions of this result. In the first, we provide a large set \cal A of non-self-orthogonal vectors of \mathbbFd such that for every two subsets of \cal A of size k+1 each, some vector of one of the subsets is orthogonal to some vector of the other. In the second extension, every k+1 vectors of the produced set \cal A include ℓ+1 pairwise orthogonal vectors for an arbitrary fixed integer 1 ≤ ℓ ≤ k. The proofs involve probabilistic and spectral arguments and the hypergraph container method.