All Questions
Tagged with design-theory or combinatorial-designs
125 questions
2
votes
3
answers
319
views
Constructions of $2-(v,3,3)$-designs
I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...
- 11
1
vote
1
answer
834
views
Known results on cyclic difference sets
Is there any infinite family of $v$ for which all the $(v,k,\lambda)$-cyclic difference sets with $k-\lambda$ a prime power coprime to $v$ have been determined?
A subset $D=\{a_1,\ldots,a_k\}$ of $\...
- 767
3
votes
1
answer
427
views
Ranks of higher incidence matrices of designs
In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is
$$
Rk_{2}(N)=v-(d_{p}+1),
$$
where $d_{p}$ is the ...
- 3,692
4
votes
2
answers
620
views
Is Ryser's conjecture on permanent minimizers still open?
Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$.
Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ ...
- 37.7k
11
votes
4
answers
5k
views
Constructing Steiner Triple Systems Algorithmically
I want to create STS(n) algorithmically. I know there are STS(n)s for $n \cong 1,3 \mod 6$. But it is difficult to actually construct the triples. For STS(7) it is pretty easy and but for larger n I ...
- 3,692
-1
votes
1
answer
394
views
Number of blocks in a t-(v,k,l) design with empty intersection with a given set U [closed]
Question
Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$?
The answer is: $\...
CommunityBot
- 1
2
votes
1
answer
169
views
Lower bounds on cardinality of a union of blocks in a design
Let $D$ be a $(v,k,\lambda)$-design (repeated blocks are allowed). I would like to get a lower bound on the cardinality of the union of $s$ blocks. A naive application of inclusion-exclusion gives $sk-...
- 6,962
22
votes
1
answer
2k
views
Octonions and the Fano plane.
Does the Fano plane mnemonic for octonion multiplication have any deeper meaning?
http://upload.wikimedia.org/wikipedia/commons/2/2d/FanoPlane.svg
The symmetry group of the Fano plane is PSL(2,7), ...
- 151
7
votes
0
answers
188
views
Tenacious structure
Let $\def\A{\mathbb A}\def\F{\mathbb F}\F_3$ be the Galois field with three elements and let $\A^d=\A^d(\F_3)$ be the affine space of dimension $d$ over $\mathbb F_3$ —the subject is combinatorics and ...
- 47.3k
3
votes
3
answers
707
views
Orthogonal Latin Square 6*6
I need to make remarks about Tarry's Proof for the nonexistence of 6x6 Latin Squares as part of my final exam for a class I'm in. Problem is, I can't find it ANYWHERE on the internet. I can only find ...
- 5,432
2
votes
2
answers
298
views
Resolvable designs from projective space
Resolvable designs are block designs with the additional property that the blocks can be partitioned into partitions of the points. It is easy to see that lines in affine space form a resolvable ...
- 3,692
1
vote
5
answers
374
views
Pairwise balanced designs with $r=\lambda^{2}$
A while ago I asked how to construct an infinite family of $(v,b,r,k,\lambda)$-designs satisfying $r=\lambda^{2}$ and got very good answers from Yuichiro Fujiwara and Ken W. Smith.
Now I'd like to up ...
CommunityBot
- 1
4
votes
2
answers
331
views
Is there an infinite number of combinatorial designs with $r=\lambda^{2}$
A quick look at Ed Spence's page reveals two such examples: (7,3,3) and (16,6,3).
If there is a known classification and/or name by which such designs go, I'd love to know about them too.
EDIT: I ...
- 3,692
5
votes
1
answer
322
views
Block design question
Given fixed values for $d \leq k \leq v$. I would like to find a set $B$ of $d$-sets of $[v]$ with the following properties:
Every $k$-set of $[v]$ contains at least one element of $B$
Every element ...
- 3,692
12
votes
5
answers
569
views
Intersecting 4-sets
Is it possible to have more than $N = \binom{\lfloor n/2\rfloor}{2}$ subsets of an $n$-set, each of size 4, such that each two of them intersect in 0 or 2 elements?
To see that $N$ is achievable, ...
- 32.1k
2
votes
1
answer
427
views
Popular elements in cross-intersecting families
Let $\mathcal{T}$ and $\mathcal{S}$ be two families of subsets of $[n]$ such that for all $T_i\in \mathcal{T}$ and $S_j\in \mathcal{S}$,
$|T_i \cap S_j| \neq\emptyset$
$|T_i| , |S_j| \leq t = O(\log(...
CommunityBot
- 1
3
votes
1
answer
1k
views
Residual design (BIBD) with repeated blocks
Simple BIBD are defined as those designs in which incindence relation is "is element". So effectively blocks are subsets of points. Equivalently there should be no "repeating blocks" ie. blocks that ...
6
votes
3
answers
678
views
Meeting management
A friend wants to have ten meetings of six people every day for five days with no pair of people meeting twice. Is this possible? It appears to be a question about maximal decomposition of a complete ...
- 30.1k
23
votes
2
answers
3k
views
Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?
The following problem is homework of a sort -- but homework I can't do!
The following problem is in Problem 1.F in Van Lint and Wilson:
Let $G$ be a graph where every vertex
has degree $d$. ...
- 30.1k
1
vote
1
answer
461
views
The Symmetry of Steiner System S(5,8,24)
The group of automorphisms of S(5,8,24), M_{24}, is 5-transitive.
Other than Symmetric groups are there any other 5-transitive groups?
If not, would it be correct to say S(5,8,24) is the most ...
- 6,614
3
votes
1
answer
275
views
Lower bounding the maximum size of sets in a set family with union promise
The following problem has come up while working on the relationship between certificate and randomized decision tree complexities of boolean functions. However, I think it is of interest by itself and ...
- 3,209
3
votes
2
answers
1k
views
How many elements with a hamming distance of 3 or less?
[This is a complete rewrite which makes some of the comments redundant or irrelevant.]
Take a set of $50$ elements. How many subsets of size $5$ are needed so that every subset of size $5$ will ...
- 30.1k
12
votes
1
answer
939
views
Which Steiner systems come from algebraic geometry?
This question is motivated by the ongoing discussion under my answer to this question. I wrote the following there:
A $(p, q, r)$ Steiner system is a collection of $q$-element subsets $A$ (called ...
CommunityBot
- 1
4
votes
1
answer
1k
views
Solving a Diophantine equation related to Algebraic Geometry, Steiner systems and $q$-binomials?
The short version of my question is:
1)For which positive integers $k, n$ is there a solution to the equation $$k(6k+1)=1+q+q^2+\cdots+q^n$$ with $q$ a prime power?
2) For which positive ...
CommunityBot
- 1
13
votes
2
answers
780
views
Is there a tournament schedule for 18 players, 17 rounds in groups of 6, which is balanced in pairs?
We are interested in a solution to the following scheduling problem, or any information about how to find it or its existence. This one comes from real life, so you will not only be helping a ...
- 233