11

Unfortunately, no. It is known that the maximum number of mutually disjoint $S(4,5,11)$s on the same point set is $2$. Any such pair are always isomorphic. So, you can't find $7$ disjoint copies of an $S(4,5,11)$ in the complete $5$-uniform hypergraph on $11$ vertices (or partition it into copies); you can find only two of them at most.
E. S. Kramer, D. M. ...

answered Jun 8 '14 at 18:15

Yuichiro Fujiwara

3,58211 gold badge2222 silver badges4242 bronze badges

10

Here is a bit more symmetric version of the picture in the accepted answer:

answered Oct 24 '21 at 18:44

Anton Petrunin

37.3k66 gold badges107107 silver badges232232 bronze badges

10

Fort and Hedlund determined the minimum size of a $(v,3,2)$-covering design: Minimal coverings of pairs by triples, Pacific J. Math. 8(4), 709-719, 1958.
The case $(v,4,2)$ was solved by Mills: On the covering of pairs by quadruples I, JCTA 13, 55–78, 1972 and II, JCTA 15, 138–166 (1973).
For the case $(v,5,2)$ with $v\equiv 0\pmod 4$, Abel, Assaf, ...

answered Jan 3 '15 at 21:18

Thomas Kalinowski

2,88622 gold badges1515 silver badges2222 bronze badges

9

Such difference sets exist. There exist (nontrivial) difference sets with
$|G| = q^{d+1}[1+(q^{d+1}-1)/(q-1)]$,
$|D| = q^d(q^{d+1}-1)/(q-1)$,
$\lambda = q^d(q^d-1)/(q-1)$,
whenever $q$ is a prime power (R. L. McFarland, A family of difference sets in non-cyclic groups, JCT A, 15 (1973), pp. 1-10). More precisely, such difference sets exist in any ...

9

The answer to the first question is "no." Suppose $|M|=11$ and $\mathcal S\subset\binom M5$ and $|\mathcal S|=77.$ Since each $5$-set contains five $4$-sets, and since $77\cdot5=385\gt330=\binom{11}4,$ by the pigeonhole principle some $4$-set must be contained in two members of $\mathcal S,$ which are both contained in the same $6$-set.

9

I claim that $S_{k,n}=2^k$ for all $n\geqslant k$. Moreover, $\sum 2^{-m_i}\leqslant 1$ if the set of strings satisfies this condition, and $m_i$ denotes the number of zeros/ones in $i$-th string.
Proof. Toss a coin for each location and consider the following events enumerated by your strings: if the string has 1/0 at some location, the corresponding coin ...

answered Dec 6 '20 at 19:19

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

8

Suppose $\Omega = \{0,1\}^{128}$ is partitioned into $N$ different sets $S_j$, with $|S_j|/|X| = p_j$. Suppose
you take $n$ random pairs of points of $\Omega$ and see how many of these pairs can't be distinguished (presumably because they are in the same partition).
The probability that two given points are in the same partition is $S_2 = \sum_{j=1}^N p_j^2$...

8

Edit: The possible "gap" of sort in Caro and Yuster's proof of their upper bound has just been fixed! See Ben Barber's comment below (and his joint paper with Daniela Kühn, Allan Lo and Deryk Osthus on arXiv. This shows Gustavsson's theorem (whose proof by Gustavsson himself might have been regarded as incomplete but was used by Caro and Yuster). So this ...

answered Jan 3 '15 at 23:39

Yuichiro Fujiwara

3,58211 gold badge2222 silver badges4242 bronze badges

8

Switching to complements, the question is if we can choose 77 6-subsets of an 11-set $M$ such that any 5-subset of $M$ is contained in a chosen 6-subset (it is clear that this subset would be unique because $77\cdot 6 = \binom{11}{5}$). These are called covering designs and the question is if $C(11,6,5)=77$.
The answer is "No". In fact, it is known that
$$...

8

Here's at least a couple of candidate designs which have the first four properties, although I haven't checked acyclicity and don't yet see how to exploit the existing symmetries to check it other than by a brute-force rank computation of the boundary map.
(1) The orbit of the set $\{ \infty, 0, 1, 2 \}$ under the fractional-linear action of $G=\mathrm{PSL}...

7

An elementary counting argument shows that $2$-$(v,3,3)$ exists only if $v$ is odd (or, more precisely, for $\lambda \equiv 3 \pmod{6}$ a $2$-$(v,3,\lambda)$ exists only if $v \equiv 1 \pmod{2}$). This necessary condition is sufficient.
Arguably the simplest direct construction for the case $\lambda = 3$ that covers all odd $v$ is to use commutative ...

answered Dec 10 '13 at 16:33

Yuichiro Fujiwara

3,58211 gold badge2222 silver badges4242 bronze badges

7

It is called perfect hash families in the design theory and computer science literature.
A perfect hash family PHF$(N; k, v, t)$ is an $N \times k$ array on $v$ symbols with $v \geq t$,
where for every $N \times t$ subarray at least one row consists of distinct symbols. The following shows a PHF$(6; 12, 3, 3)$.
$$\left[
\begin{array}{cccccccccccc}
1&0&...

answered Jun 20 '14 at 14:57

Yuichiro Fujiwara

3,58211 gold badge2222 silver badges4242 bronze badges

7

Well, interestingly enough, all the 80 Steiner triple systems on 15 points have minimum dominating sets of size 10 - there is more tradeoff between the points/blocks than I first recognised.
But if we go a bit bigger then we can find some variation. Here is a $2$-$(25,4,1)$ design with 50 blocks.
0 1 2 3; 0 4 5 6; 0 7 8 9; 0 10 11 12; 0 13 14 15; 0 16 17 ...

7

You could try "Stinson - Combinatorial design theory" too. Also, just in case it might interest you: I am half-learning design theory myself and trying to implement the constructive proof of existence that I find in the software Sage.
The goal is to be able to actually build all the combinatorial designs which exist in the litterature. I'd be delighted to ...

7

There is a list of references in
http://www.maths.qmul.ac.uk/~pjc/design/resources.html#books
and
http://en.wikipedia.org/wiki/Block_design#References
From the latter, I know books by Beth et al (a long and detailed) and by Hughes and Piper (shorter and more readable).
All of it is outdated in several important aspects, e.g. the huge progress on ...

6

If $n$ is odd, the answer is $\lceil \binom{n}{2}/4 \rceil$.
If $n$ is even, the answer is $\lceil \binom{n}{2}/4+n/8 \rceil$.
This follows from two special cases of a more general conjecture by Alspach.
For our purposes, we use a theorem of Heinrich, Horák, and Rosa which says that if $n \geq 7$ is odd and $a,b,c$ are such that $3a+4b+6c=\binom{n}{2}$, ...

6

Let me address the case $k=N/2$. Consider a hypergraph whose edges are your groups. Then, basically, you are interested in the discrepancy of your hypergraph. The first estimate at the linked Wikipedia page, $\textrm{disc}\leq \lambda=\sqrt{2N\ln 2m}$, where $m$ is the nunber of edges, shows that you cannot guess more than $N/4+O(\sqrt{N\ln N})$ by a ...

5

There is a construction given in Theorem II.2.2.10 of the Handbook of
Combinatorial designs for a STS of order a prime of form $6t+1$. It is clear
that the resulting STS has a cyclic automorphism acting fixed-point-freely on
points. The other STS of order 13 has a full automorphism group isomorphic to $S_{3}$.
So the automorphism group could be a good ...

5

Here are some solutions for the largest possible set of conditions, $n=2k$.
Suppose $p$ is a prime that divides ${2k\choose k}, {2k-1\choose k-1}, \ldots, {k+1\choose 1}$. Then the selection conditions in your question (that is, $b={2k\choose k}/p$ blocks, with each element in $r={2k-1\choose k-1}/p$ of them, and each pair in ${2k-2\choose k-2}/p$, etc.) ...

5

Personally, I am most interested in design theory with an "asymptotic flavor", and I think there are (edit: were, pre-Keevash) some very interesting open questions in this direction.
To cut to the chase, I think asymptotic design theory today is effectively searching for a constructive proof of Gustavsson's Theorem: All "admissible" graphs $G$ which are ...

5

With all due respect to Colin McLarty, here is (in my not so humble opinion) a better answer.
The conjecture (For every positive integer $k,$ there is a square matrix $H$ of order $4k$ such that $H$ is binary with entries being $1$ or $-1$, with $HH^t = 4k~I$) is not resolved, but there is much work going on in the area.
The conjecture is generalized to ...

5

Linear algebra is also useful for proving lower bounds in extremal "bootstrap percolation" type problems. For example, Alon and Kalai used linear algebra (actually, exterior algebra) to (independently) answer the following question, first considered by Bollobás:
What is the minimum number of edges in a graph $G$ on $n$ vertices such that the non-edges of $G$...

5

This is a coding theory question. You want to find a binary constant weight $m$ code with $k$ codewords, and of maximal possible distance.
There was a lot of research done on this.
For the specific case of $k$ small compared to $n$, one can take sufficiently many copies of a nice constant weight code with $k$ words.
E.g. for $k=14$ you can take the the ...

5

The question is a little ambiguous as to what it is asking. But the idea is clear and it is a nice question. As I interpret it, I think the answer might be no and that designs and finite geometries might provide examples.
Since you want the guaranteed score ,not the expected one, I interpret your problem as this: We select some number $c$ of $k$ element ...

answered Sep 18 '19 at 21:43

Aaron Meyerowitz

28.9k11 gold badge4040 silver badges9797 bronze badges

5

Let me get started with a small take at question 3, by proving that for $v\le 6$, the complete quadrilateral is optimal.
First, for $v\in\{1,2,3\}$ it is clear that no pooling design can have compression rate $r<1$ (so trivial is optimal). For example for $v=3$, we need to distinguish at least $5$ situations (no positives, at least $2$ positives, and $3$ ...

5

This isn't a full answer, but too long for a comment. I suppose it comes closest to trying to answer Question 3 or the general question of whether the hypercube design can be improved.
Definition Given a hypergraph $G=(\{v_1, \dots, v_n\}, E)$, the dual of $G$ is the hypergraph $H$ with $V(H)=E(G)$ and $E(H)=\{\{e\in E(G): v_i\in e\}: i\in [k]\}$ (in other ...

4

Variants of the EKR Theorem offer a wide class of examples. This page has a nice list going, by the way.
A friend of mine once made the outrageous claim -- but hear me out -- that most "linear algebra proofs" in combinatorics are not truly using linear algebra. I think he was getting at such arguments' use of a preferential basis (think positive or $\{0,1\...

4

A periodic $(n,k)$ coloring can be modified to give a non-periodic $(mn+\ell,mk+\ell)$ coloring for any non-negative $m,\ell$ not both $0$ (this uses some comments to improve my previous answer, although there seem to be even better answers given) ). This is a modification of Anthony's construction without need of probabilities. This allows the periodic $(3,...

4

No there are non-periodic colourings of this type.
Start off with a periodic $(n,k)$ lattice colouring and generate a new $(2n,2k)$ lattice colouring by splitting each of the $n$ colours into two "hues". Let the original colours be $\{2,4,6,\ldots,2n\}$ and the new colours be $\{1,2,3,\ldots,2n\}$.
If $\xi$ is your original lattice colouring, you can make ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

combinatorial-designs × 99co.combinatorics × 82

graph-theory × 10

steiner-triple-system × 7

linear-algebra × 6

hypergraph × 6

extremal-combinatorics × 5

nt.number-theory × 4

reference-request × 4

discrete-geometry × 4

coding-theory × 4

incidence-geometry × 4

ag.algebraic-geometry × 3

gr.group-theory × 3

matrices × 3

algorithms × 3

finite-fields × 3

open-problems × 3

latin-square × 3

set-theory × 2

graph-colorings × 2

projective-geometry × 2

matrix-theory × 2

finite-geometry × 2

at.algebraic-topology × 1