2
$\begingroup$

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.

We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we have:

  • $|A_i|=t$ for every $A_i\in W$;
  • $|A_i\cap A_j|\leq 1$ for every $A_i, A_j\in W$ with $i\neq j$;
  • $W$ is maximal with respect to $\subset$.

(Sorry for the name quasi-partition but I didn't know how to name this kind of sets)

I would like to determine (or to give an upper bound) the number

$$a_{n,t}:= \max_{W \;q-p\; of \; A } |W| $$

Note: This problem should be equal to finding the clique number $\omega(G)$ of the graph $G$, where $G$ is the generalized Kneser graph $KG(n,t,1)$. An upper bound could be given by its chromatic number $\chi(G)$. If $n=(t-1)s+r$ with $0\leq r < t-1$
$$ \chi(G) = (t-1)\dbinom{s}{2}+rs,$$ (see http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190090204/abstract, but unfortunately I don't have the permission to get it) but I don't think it is an optimal bound.

Could anybody help me? Thanks in advance for every comment.

$\endgroup$
  • 3
    $\begingroup$ See mathoverflow.net/questions/161159/… $\endgroup$ – Lucia Sep 13 '14 at 14:30
  • 1
    $\begingroup$ This question is very similar to the one Lucia linked, but the other question asked for asymptotics instead of exact values or upper bounds. I'm not voting to close as a duplicate because Lucia's accepted answer to the other question may not be an answer to this question. $\endgroup$ – Douglas Zare Sep 13 '14 at 15:11
  • $\begingroup$ @DouglasZare: Actually my answer there gave an explicit upper bound which is tight in some cases. $\endgroup$ – Lucia Sep 13 '14 at 15:21
  • 1
    $\begingroup$ @Lucia: Yes, that upper bound is basic and does help to answer this question. Ideally, we would like to determine the values, and I think it needs to be stated that many of the values are well-known open problems (such as when projective planes exist), while others are well-known solved problems (such as when Steiner triple systems exist). The part about $t \gt 2$ (for a different $t$) is a tangent that doesn't help here. $\endgroup$ – Douglas Zare Sep 13 '14 at 15:26
  • 1
    $\begingroup$ Actually I'm interested in understanding what happens when $A=\mathbb F_q^*$ where $\mathbb F_q$ denotes the finite field with $q=p^k$ elements. $\endgroup$ – Sfarla Sep 13 '14 at 15:43
7
$\begingroup$

Lucia's answer given in the linked question from the comment gives an upper bound (i.e., no pair should appear twice as a subset of $A_i$). But of course, the real question starts from here:

When can we attain the upper bound? When we can't, what's the largest cardinality of $W$?

The question as stated (without taking into account the focus on the case of $\mathbb{F}_q^*$ OP stated in the comment) is a duplicate of this question What is the largest number of k-element subsets of a given n-element set S such that… (which is not the same one as Lucia linked to). And the answer I gave there and another answer given in the question linked from there summarize what is currently known for the general case you explicated asked.

The question can be naturally stated in various equivalent ways, e.g., the size of a maximal packing of fixed block size in design theory, the largest uniform semilinear space (aka partial linear space and near-linear space) in incidence geometry, the largest uniform hypergraphs avoiding $2$-cycles in graph theory, and the largest binary constant-weight code of length $n$, constant weight $t$, and minimum distance at least $2(t-1)$ in coding theory. So you may be able to find more information if you search MO or google with these keywords.

Before considering the special case OP mentioned in the comment, here's a quick summary of what's current known for the general case:

The strongest general upper bound is:

$$a_{n,t}\leq\left\lfloor\frac{n}{t}\middle\lfloor\frac{n-1}{t-1}\middle\rfloor\right\rfloor.$$

This is a corollary of the Johnson bound (which is proved by S.M. Johnson in A new upper bound for error-correcting codes, IRE Trans. IT-8 (1962) 203–207).

This is best possible because there are infinitely many examples that attain this bound. For example, a Steiner $2$-design of order $n$ and block size t is an ordered set $(A, \mathcal{B})$ of finite sets $A$ and $\mathcal{B}$ such that $\vert A\vert = n$ and $\mathcal{B}$ is a family of $t$-subsets of $A$ in which every pair of elements in $A$ appears exactly once as a subset of $B\in\mathcal{B}$. Trivially $\mathcal{B}$ is a quasi-partition $W$ attaining the bound $a_{n,t}\leq\frac{n(n-1)}{t(t-1)}$. Their asymptotic existence is known:

There exists a constant $n_t$ that depends only on $t$ such that for all $n > n_t$ such that $\frac{n(n-1)}{t(t-1)}$ is an integer and such that $t-1$ divides $n-1$, there exists a Steiner $2$-design of order $n$ and block size $t$.

The above result is a corollary of Wilson's Fundamental Existence Theorem. The two conditions $n(n-1) \equiv 0 \pmod{t(t-1}$ and $n-1 \equiv 0 \pmod{t-1}$ are necessary conditions for the existence (so this is an asymptotic answer to the question).

This is already a remarkable result on a difficult problem. But even tougher are when $\frac{n(n-1)}{t(t-1)}$ isn't an integer as well as when $n$ isn't quite large enough for the asymptotic result to kick in. For the former case, the best know general result is proved here:

Y. M. Chee, C. J. Colbourn, A. C. H. Ling, R. M. Wilson, Covering and packing for pairs, J. Combin. Theory Ser. A 120 (2013) 1440–1449.

(If you're blocked by the paywall, you might want to google the title of the paper.) A quick summary of the relevant result is that the Johnson bound is essentially correct in that the largest number $a_{n,t}$ is within an additive constant from the upper bound. For the latter tougher case, you can find a comprehensive list of known results in the Handbook of Combinatorial Designs.

If you're only interested in explicit constructions for optimal $W$ by taking advantage of finite fields via assuming $A=\mathbb{F}_q^*$, a straightforward way is to take the points and lines of projective geometry $\operatorname{PG}(d,2)$ as $A$ and $W$ respectively. This gives you a Steiner $2$-design of order $2^{d+1}-1$ and block size $3$ in which the cyclic group $\mathbb{F}_{2^{d+1}}^*$ acts regularly on $A$ (i.e., there is a Singer cycle).

Another classic construction is due to

Netto, Zur Theorie der Triplesysteme, Math. Ann. 42 (1893), 143--152:

Let $q = 6t+1$ be a prime power that is $1$ modulo $6$ and $\mathbb{F}_q$ the finite field on a set $X$ of size $q$ with $0$ as its zero element. Take a primitive root $\omega$ of unity. Let

$$\mathcal{B} = \{\{\omega^i+j, \omega^{2t+i}+j, \omega^{4t+i}+j\} \mid 0\leq i\leq t, \ j \in X\}.$$

Then $(X, \mathcal{B})$ is a Steiner $2$-design of order $q$ and block size $3$. Deleting all $B \in \mathcal{B}$ with $0 \in B$ gives a quasi-partition $W$ of size $\frac{q(q-1)}{6}-\frac{q-1}{2}=\frac{(q-1)(q-3)}{6}$, which can be verified to be largest possible.

You can use the same technique of deleting $0$ from Steiner $2$-designs over $\mathbb{F}_q$ with a larger block size for obtaining more optimal $W$ over $\mathbb{F}_q^*$. For example, let $q = 12t+1$ be a prime power and $\omega$ a primitive root of $\mathbb{F}_q$ such that $\omega^{4t}-1=\omega^{r}$ with $r$ odd. Then,

$$\mathcal{B}=\{\{j,\omega^{2i}+j,\omega^{2i+4t}+j,\omega^{2i+8t}+j\} \mid 0\leq i\leq 2t-2, \ j\in\mathbb{F}_q\}$$

forms a Steiner $2$-design of order $q$ and block size $4$ (when taken together with whatever set you use for the finite field). Again, deleting all $B \in \mathcal{B}$ that contains the zero element gives you $W$ over $\mathbb{F}_q^*$, which can be verified to be optimal. (I don't know who first gave this construction, but this is a well-known result in design theory.)

I am not aware of a general framework that unifies this type of approach for general $t$ and $q$. It'd be nice if we could understand what's going on in these similar constructions, though... In any case, there are more constructions like these. And they are generally presented as constructions for balanced incomplete block designs (BIBD) in the literature.

Of course, if you don't need to exploit finite fields and just want the set $A$ to be $\mathbb{F}_q^*$, possibilities are limitless because you can just replace the set $A$ with $\mathbb{F}_q^*$ after constructing a maximal packing (or uniform hypergraph avoiding $2$-cycles, largest constant-weight code, etc.) over an arbitrary set.

An optimal optical orthogonal codes of index $1$ happens to be equivalent to a maximal packing $(A,\mathcal{B})$ in which a cyclic group acts regularly on $A$. So, this line of research may give you what you're looking for, too. But as far as I know, the existence problem of a Steiner $2$-design $(A,\mathcal{B})$ in which the cyclic group $\mathbb{Z}_n$ acts regularly on $A$ is still open even for block size $4$. (The case when the block size is $3$ is Heffter's difference question and was solved in the 19th century). So, the analogous question for packings, which seems much harder, should be wide open.

$\endgroup$
  • 1
    $\begingroup$ In your statement of Wilson's theorem don't you need the condition that $t-1$ divides $n-1$? $\endgroup$ – Lucia Sep 14 '14 at 3:53
  • $\begingroup$ @Lucia Ah, yes! I forgot to include the other necessary condition. Thank you for pointing it out! $\endgroup$ – Yuichiro Fujiwara Sep 14 '14 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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