9
$\begingroup$

Is there a theory from which the following problem comes? Does this type of problem have a name?

Find the largest possible number of $k$-element sets consisting of points from some finite set and have pairwise singleton or empty intersections.

I hope that was clear. If not, here's an example for $k=3$:

Let the set of points be $S=\{1,2,3,4,5,6\}$. The most 3-element sets (with pairwise singleton or empty intersections) that can be constructed from $S$ is 4, such as $\{456,236,124,135\}$.

I made a table for $|S|=3,4,5,6,7,8,9$ and got $1,1,2,4,7,8,12$, respectively, hoping I could dig up some information from OEIS.

I read a little on Steiner systems, and although it feels like I'm in the neighborhood, I'm not confident...

Edit1: typos.

Edit2: Johnson graphs and (for $k=3$) Steiner Triple Systems (STS) seem close to what I'm looking for. The condition of "pairwise singleton or empty intersections" is equivalent to "every 2-subset of S occurs in at most one $k$-element set". STS require that every 2-subset of S occurs in exactly one $3$-element set".

Edit3: Thank you to everyone who replied! All of your comments helped me push through a barrier I was facing for some time.

$\endgroup$
5
  • 1
    $\begingroup$ Looks a bit like a Johnson graph. Perhaps looking at some of the more popular objects in finite geometry will get you graphs matching your own $\endgroup$ Commented Feb 19, 2013 at 20:00
  • $\begingroup$ Design theory is also relevant $\endgroup$ Commented Feb 19, 2013 at 23:30
  • 1
    $\begingroup$ The $k=3$ sequence seems to be oeis.org/A001839 . $\endgroup$ Commented Feb 19, 2013 at 23:51
  • $\begingroup$ @KevinCostello is correct; and the term for $|S|=8$ should be $8$, not $7$. For example, the eight elements of $[[1,3,8],[1,4,7],[1,5,6],[2,3,7],[2,4,6],[2,5,8],[3,4,5],[6,7,8]]$. $\endgroup$ Commented Feb 20, 2013 at 0:50
  • 2
    $\begingroup$ In general, you are looking for the maximal code of length $n$, constant weight $k$, and minimum distance $2k-2$. So the $k=4$ sequence is $A(n,6,4)$, found at oeis.org/A004037. $\endgroup$ Commented Feb 20, 2013 at 0:57

3 Answers 3

Reset to default
2
$\begingroup$

You exactly want to determine the clique number of the generalized Kneser graph $KG_{n,k,s}$ for $s=1$, which is the graph having all the $k$-element subsets as its $\binom{n}{k}$ vertices, where any two vertices are connected if and only if their cut contains at most $s$ elements. Thus, a maximum clique of $KG_{n,k,1}$ is a maximum selection of $k$-element subsets such that all their pairwise cuts are singleton or emtpy. The size of such a maximum clique is the clique number $\omega(KG_{n,k,s})$.

Googling around a bit, I could not find an exact expression therefore.

However, this states that $\omega(KG_{n,k,0}) = \lfloor \frac n k \rfloor$. Since for $s > 0$ edges are never removed, this also gives a lower bound on $\omega(KG_{n,k,s})$ for any $s \geq 0$, thus, $\omega(KG_{n,k,1}) \geq \lfloor \frac n k \rfloor$. But this bound seems rather weak, since it does not respect any singleton edges at all. For your example above we get 1,1,1,2,2,2,3 as lower bounds on 1,1,2,4,7,7,12.

Further, here is an expression for the chromatic number $\chi(KG_{n,k,1})$, which gives an upper bound on the clique number, since $\chi(G) \geq \omega(G)$ for any graph $G$, where for perfect graphs equality holds. For $n$ written as $n = (k-1) s + r$ for some $0 \leq r < k-1$ and large enough $n > n_0(k)$, the bound is given as $\chi(KG_{n,k,1}) = (k-1)\binom{s}{2} + rs \geq \omega(KG_{n,k,1})$. Ignoring any details on $n_0(k)$, since I have no access to the paper, this gives 1,2,4,6,9,12,16 as upper bounds on 1,1,2,4,7,7,12, which seems to approximate quite well.

Perhaps one of the proofs behind the above results can be adopted to the clique number of $KG_{n,k,1}$?

edit: I just realized that you even want to find a maximum clique - well, that is computationally very hard in general, but perhaps things get easier for $KG_{n,k,1}$?

$\endgroup$
2
$\begingroup$

If you're interested in the asymptotic situation instead of what happens for specific $|S|$, then this has been studied a fair bit under the name of packing problems. More generally, we can ask the question of the size of the largest collection of $k$-element subsets of $\{1, \dots, n\}$ such that each pair of subsets has intersection of size strictly less than $r$.

Since each $k$-element subset contains $\binom{k}{r}$ $r$-element subsets, and each $r$ element subset is in at most $1$ $k$-element subset, we can pick at most $$\frac{\binom{n}{r}}{\binom{k}{r}}$$ subsets in our collection.

Erdos and Hanani conjectured in 1963 that this was asymptotically optimal: For fixed $k$ and $r$, as $n$ tends to infinity, there is a collection of size $(1+o(1))$ times the bound above (for the specific case $r=2$ that you mentioned, this was conjectured earlier by Bose). The conjecture remained open for more than $20$ years until Rodl introduced his so-called "nibble method" to prove it ("On a Packing and Covering Problem", not available online as far as I can tell).

Another term you might want to search under is partial Steiner systems.

$\endgroup$
1
1
$\begingroup$

A family of subsets of some finite set is a hypergraph; the subsets themselves are the edges (or hyperedges) of the hypergraph. If all the edges have size $k$, then the hypergraph is k-uniform. (For instance, a $2$-uniform hypergraph is just an ordinary undirected graph.) If no pair of edges has more than one point in common, the hypergraph is called linear. So your question can be reframed as:

What is the maximal number of edges in a $k$-uniform linear hypergraph on $n$ vertices?

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.