Cone dependence -- a basic combinatorial concept

DOI10.1023/A:1024183804420MaRDI QIDQ1404310zbMATH OpenOpenAlexWikidataFDO

Authors Levon H. Khachatrian, Rudolf Ahlswede

Publication date 21 August 2003

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1024183804420

zbMATH Keywords

binary sequencecombinatorial extremal problemspositive linear combinationsTurán problem

Mathematics Subject Classification ID

Other designs, configurations (05B30) Extremal set theory (05D05) Discrete geometry (52C99)

Review text

A set \(A \subset \mathbb{R}^n\) is cone independent of \(B \subset \mathbb{R}^n\) if no \(a \in A\) is a non-negative linear combination of \(B \setminus a.\) If \(B=A\) then \(A\) is called a cone independent set. Denote \(P(n)\) the set of all cone independent \((0,1)\)-vector subsets of \(\mathbb{R}^n.\) Furthermore denote \(P_n(k,\ell)\) the set of all \((0,1)\)-vector subsets of \( \mathbb{R}^n,\) such that every vector in \(A\in P_n(k,\ell)\) has exactly \(k\) ones, and every \((0,1)\)-vector with exactly \(\ell\) ones is cone independent of \(A.\) The aim of this paper is to determine the maximum possible cardinalities \(c(n)\) in \(P(n)\) and \(c_n(k,\ell)\) in \(P_n(k,\ell).\) These new concepts are hard: for example the value \(c_n(k,k+1)\) coincides with the Turán number \(\tau_n(k,k+1).\) The paper proves that \(\lim_n c(n)/2^n\) exists and is in between 0.55 and 1. The conjecture is that the limes is less than 1. The authors determine two special cases of \(c_n(k,\ell)\) and formulate a conjecture for the general \(c_n(k,\ell).\) The proofs use classical results of Turán theory and the shifting operations of extremal set theory.

Recommendations

• scientific article; zbMATH DE number 1264586
• scientific article; zbMATH DE number 6789270
• scientific article; zbMATH DE number 1846855
• Combinatorial identities for polyhedral cones
• Combinatorial convexity
• Combinatorial properties of dependence graphs
• The cone condition and \(t\)-designs
• Combinatorics and geometry of Littlewood-Richardson cones
• Cone Inclusion Numbers
• Convexity in combinatorial structures

Cited in

(3)

• A remark on the problem of nonnegative k-subset sums
• Minimum number of edges in a hypergraph guaranteeing a perfect fractional matching and the MMS conjecture
• Fractional matchings in hypergraphs

This page was built for publication: Cone dependence -- a basic combinatorial concept

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