Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 –  muzzlator Feb 19 '13 at 20:00
    
Thanks for the tip. –  sasha Feb 19 '13 at 20:36
    
Design theory is also relevant –  mrf Feb 19 '13 at 23:30
1  
The $k=3$ sequence seems to be oeis.org/A001839 . –  Kevin Costello Feb 19 '13 at 23:51
1  
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. –  mjqxxxx Feb 20 '13 at 0:57

3 Answers 3

up vote 1 down vote accepted

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}$?

share|improve this answer

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?

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.