2
$\begingroup$

We consider any non-negative integer $n$ as a cardinal, so $0 = \emptyset$, and $n=\{0,\ldots,n-1\}$ for positive $n$. Given $n,k\in \mathbb{N}$, let $[n]^k$ denote the collection of $k$-element subsets of $n$. We say ${\cal L}\subseteq [n]^k$ is linear if $|a\cap b|\leq 1$ whenever $a\neq b\in {\cal L}$, and we call ${\cal L}$ maximal linear if ${\cal M}\subseteq [n]^k$ is no longer linear whenever ${\cal M}\supseteq {\cal L}$ and ${\cal M}\neq {\cal L}$.

Given integers $n\geq k\geq 1$, what is the minimum cardinality of any maximal linear subset of $[n]^k$, and what is the maximum cardinality, in terms of $n,k$?

$\endgroup$
2
  • $\begingroup$ Perhaps the maximum cardinality (a much investigated set packing problem) and the minimum cardinality should be two separate questions. $\endgroup$
    – bof
    Commented Nov 2, 2021 at 17:24
  • 1
    $\begingroup$ For the "maximum" question see the discussion of $D(t,k,v)$ for $t=2$ in A. E. Brouwer, Packing and Covering of $\binom kt$-sets, Mathematical Centre Tracts 106 (1979), 89-97 for a comprehensive survey of what was known 40 years ago. $\endgroup$
    – bof
    Commented Nov 2, 2021 at 17:45

1 Answer 1

4
$\begingroup$

For the minimum question, this is answered in Theorem 4 of Erdős, Paul; Füredi, Zoltán; Tuza, Zsolt, Saturated (r)-uniform hypergraphs, Discrete Math. 98, No. 2, 95-104 (1991). ZBL0766.05060.

The answer is $\frac{n^2}{k(k-1)^2}+\Theta(n)$ (which is roughly a $\frac{1}{k-1}$ proportion of the maximum possible $\frac{n(n-1)}{k(k-1)}$), and you can get something a bit more precise from their proof if you need.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .