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.



On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections
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…](https://mathoverflow.net/q/132263/27829) (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](https://mathoverflow.net/q/132372/27829) 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](http://en.wikipedia.org/wiki/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.](http://dx.doi.org/10.1016/j.jcta.2013.04.005)


(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](http://www.emba.uvm.edu/~jdinitz/hcd.html).


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](http://dx.doi.org/10.1007/BF01443448):


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.


