Questions tagged [combinatorial-designs]
For questions about Combinatorial design theory, a part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. The theory has applications in the area of the design of experiments.
1
vote
1answer
17 views
Stuck on the Proof on Fisher's Inequality
I'm confused about the proof that for a balanced design with parameters $(v, b, r, k, \lambda)$, if $v \gt k$, then $b \ge v$.
If you let $M$ be the incidence matrix of the design such that $M_{ij}$ ...
1
vote
1answer
62 views
Efficient calculation of difference sets from finite fields
A while ago I wrote a program to generate, amongst other things, difference sets from finite fields. Generating these sets is rather slow. Is there some theorem or construction I could use to speed it ...
0
votes
3answers
34 views
Points in the Fano plane
Problem: Show that any two points in Fano plane are not contained in exactly two lines of the plane and their sum is contained in those two lines in which $p$ and $q$ are not contained.
My attempt:
...
0
votes
0answers
46 views
Is there an infinite class of Bose Steiner triple systems that are resolvable?
Does there exist an infinite subclass of Steiner triple systems yielded by the Bose construction that are resolvable? Recall that a Steiner triple system of order $v$ is resolvable if its block set ...
3
votes
0answers
37 views
Dinner party courses needed to have everyone sit with everyone else (repeats allowed)
There are a large number of similar questions on this site, but most of them seem to have an additional constraint that I do not have.
I am organizing a dinner party for $P$ people sitting at $T$ ...
4
votes
0answers
59 views
Arranging playdate groups
At my kids' school, the kids are meeting in playdate groups of two girls and two boys every month. The groups are constructed to get as much variation in the groups over the months. Having seen too ...
0
votes
0answers
25 views
Combinatorics Question: How can I arrange & rearrange people over n tables so that they sat with every other person at least once?
The problem is the following:
A friend of mine want's to organize an event where k people (k~30) should be distributed (seated) over n tables (n~5). After some time (possibly every ~ 4 minutes) these ...
1
vote
1answer
38 views
how to create a schedule for 9 teams playing x number of games no team can play same team twice no team can play same game twice
I am setting up a minute to win it challenge for a party. I have 9 teams of 5 players each. Each round will be head to head challenge with one team idle per round. All games are played simultaneously. ...
0
votes
1answer
28 views
Round-robin tournament scheduling where no team plays twice in a row, for n teams games
Inspired by this question here:, I would conjecture that so long as there are 2n+1 teams involved in a round-robin tournament where each games consists of n-way teams, then a schedule is possible ...
1
vote
1answer
35 views
Idempotent and commutative Latin squares of even order.
Definition: A Latin square is said to be idempotent iff $\forall i=1,\cdots, m,[(i,i)=i]$
Definition: A Latin square is said to be commutative iff $\forall i,j((i,j)=(j,i))$ such that $1\leq i,j\leq ...
2
votes
1answer
32 views
Given n teams of n people, go n rounds matching each person with different people from other teams
There a n teams of n people, where n is a natural number greater than 1. In one round, each person from each team is grouped with one person from each of the other teams. This forms n sets of n ...
0
votes
0answers
98 views
Show that if a block design of type $3-(v, 6,1)$ exists, then $v \equiv 2, or, 6 \pmod{20}$
I am stuck on this questions about block designs. All my course content has been based off 2-designs, and I have no idea how to go about answering this.
Any help would be appreciated!
0
votes
0answers
43 views
Near parallel classes, deficient points, and near resolutions
Been stuck on the question for a few days and any leads would be greatly appreciated. My thought process was for arbitrary element $x \in X$, let there be $g$ near parallel classes. These near ...
2
votes
0answers
55 views
Filling a modified sudoku/latin square
Let us build a square array in the following manner, which I would like to call a modified sudoku:
1) Every row and column contains only one copy of a positive entry and there are exactly $t$ such ...
1
vote
1answer
40 views
Generating rotating groups for a seminar
One of my teachers is planning a seminar for his English class and he asked me if there was a way to generate the groups for the days other than brute-force random generating. I really think there ...
3
votes
1answer
85 views
Does Steiner system S(2,11, 1331) exist?
Does the Steiner system $S(2,11,1331)$ exist?
I think it exists because $S(2, q, q^n)$ exists when $q$ is a prime power, $n\ge 2$. Confirmation will be very useful to me. A Steiner system forms a ...
4
votes
0answers
124 views
Count the number of sets of subsets of (Steiner?) triples
Given a set of $v$ numbers. Fix $v$. How many sets of $v$ sorted triples can be created, matching the following conditions:
two triples shall have at most one number in common
over all triples each ...
4
votes
1answer
78 views
Subsets of a set with common elements between themselves
Let $S=\{1,2,\ldots,n\}$. Let $A_i\subset S$ for $i\in\{1,2,\ldots,m\}$. Impose the following conditions
$|A_i|=r$ with $r<n$ for all $i$.
$|A_i\cap A_j|=t$ for all $i\neq j$, with $t<r$.
Let $...
1
vote
2answers
258 views
Tournament bracket for a 4-players game
for Christmas a friend is trying to organize a tournament for 13 players. Each game will be played by 4 persons, each player will play 4 games and must play against everybody else.
I can find a ...
8
votes
2answers
578 views
Trying to Solve Math Problem for Real World Use - Combinatorics
I'm trying to solve a math problem that hasn't been solved - to anyone's knowledge - in the community it's being used in. I am sure it is not difficult, but I am not smart enough to figure it out.
...
1
vote
1answer
30 views
Subsets of equal size, where each element appears an equal number of times
Suppose I have a set of N unique elements, let's say 12:
{A, B, C, D, E, F, G, H, I, J, K, L}
I would like to construct unique subsets of size X (let's say 3), such that every element in N appears ...
1
vote
1answer
56 views
Doubt in a paper on combinatorial designs
I am reading from the paper here and have a doubt in the proof of Proposition 3.8. The author says that the extensive property is immediate but I do not understand how.
The extensive property to be ...
0
votes
0answers
49 views
How many latin-square designs are orthogonal to this 4x4 latin square design
Where this Latin Square is similar to sudoku, in which each row has one and only one of 1,2,3 and 4, and each column has one and only one 1,2,3 and 4.
Important: orthogonality means that the new ...
3
votes
2answers
79 views
4-cycle decomposition of a complete graph
Let $K_n$ be the complete graph with n vertices where the number of edges $\frac {n \times (n-1)} {2}$ is a multiple of 4. Can this graph be decomposed into 4-cycles? (i.e find a partition of the set ...
0
votes
0answers
12 views
Existence of symmetric $(4t^2, t^2+\lambda, \lambda)$-BIBDs
I am dealing with symmetric balanced incomplete block designs with parameters as in the title. The parameters of every Menon design (so, $(4t^2, 2t^2-t, t^2-t)$) are of this form. I wonder, if there ...
0
votes
0answers
26 views
Compact way to prove that an incidence structure is a $t$-design
Consider the incidence structure $\mathcal{D}=(\mathcal{P},\mathcal{B},\mathcal{I})$ with point set $\mathcal{P}$, block set $\mathcal{B}$ and incidence relation $\mathcal{I}$ such that the points are ...
6
votes
2answers
153 views
Union of sets with pairwise intersection having half of the elements
Consider $k$ sets $S_1, S_2, \ldots, S_k$, of the following properties:
For every $i$, $\left|S_i\right| = p$
For every pair of $i$ and $j$, $\left|S_i \cap S_j\right| = \frac{p}{2}$
Now I need to ...
1
vote
1answer
38 views
k-subsets with some pair containing every element
Let $[n] := {1,2, 3, \dots, n}$ and $k$ be some fixed positive number.
Whats is the smallest number $m$ so that $A_1, A_2, \dots, A_m$ are k-subsets(each of size k) of $[n]$ and for every $x \in [n]$ ...
0
votes
1answer
41 views
Show that any pair of vectors jointly lies in the same number of subspaces
Assume a finite field $F_q=GF(q)$ of order $q$. Let $V$ be the $(n+1)$-dimensional vector space over $F_q$. Let $P$ be the set of 1-dimensional subspaces of $V$ i.e. $P=V\setminus\{\mathbf{0}_{(n+1)\...
6
votes
1answer
169 views
$n$-element subsets of the set $\{1,2, …, 2n\}$.
There are $\binom{2n} {n}$, $n$-element subsets of the set $\{1,2, ..., 2n\}$. I am studying the question whether one can choose from these subsets $\frac12\binom{2n} {n}$ subsets such that:
i) each ...
0
votes
0answers
21 views
On the asymptotics of Steiner triple systems that are subsystem free
A theorem of Babai, L. Babai, Almost all Steiner triple systems are asymmetric, Ann. Discrete Math. 7(1980) 37–39 asserts that a "generic" Steiner triple system is rigid, that is, has a trivial ...
2
votes
2answers
205 views
Handshake/pigeonhole principle problem?
There a number of people in a party. Each person shakes hands with exactly 20 people. For each pair of people that shakes hands with each other, there is exactly 1 other person who shakes hands with ...
0
votes
0answers
21 views
Is their any work done infinite Steiner quadruple systems?
Is there any work done on infinite Steiner quadruple systems? I know of some work by Cameron and others on infinite Steiner triple systems.
0
votes
1answer
57 views
A list of known 2-designs
I would like to know is there an update list of 2-designs? In fact, a list of known designs. Specially, is there a list of 2-(15,8,$\lambda$) designs?
-1
votes
2answers
115 views
Latin Square Problem: Indempotent Commutative Quasigroup of Order 7 [closed]
I missed the lecture that my professor went over Latin Squares and Idempotent Commutative Quasigroups. I understand it's essentially like the puzzle game Sudoku. I realize there are multiplication ...
0
votes
0answers
195 views
Block design: How to construct a 2-(16,6,2) design
For my discrete mathematics class an exercise is to look at the following square and use it to construct a 2-(16,6,2) design:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
So far my only inspiration has ...
2
votes
1answer
113 views
Arranging people for table talks (block-design-ish?)
Say you have $N$ people and $T$ tables. Each person will visit every table over the course of $T$ sessions. We want to keep the distribution of people across the tables during the sessions as even as ...
2
votes
0answers
67 views
creating a Free-For-All (1v1v1v1) schedule for 20 teams over 13 weeks
I have a project I am working on for a fantasy football league and have hit a snag that potentially could be solved with math and I'm hopeful I might find some assistance here, as I'm lost on where to ...
0
votes
0answers
33 views
A games/matches schedule [duplicate]
Suppose I have 8 teams $A_1,\ldots, A_8$, competing in different 8 games $X_1,\ldots, X_8$. For example $X_1 = soccer, X_2 = basket ball, \ldots,$
. In the morning there are 4 games $X_1,X_2,X_3,X_4$ ...
2
votes
1answer
149 views
Latin square design for a social “mixer”
I'm looking for the name of the combinatorial satisfying the following requirements:
There are $n$ different tasks.
There are $n$ different participants.
There are $n$ phases of the experiment
...
1
vote
0answers
83 views
Combinatorial proof/interpretation of derived block design parameters
I tried to solve the following exercise:
Suppose $(V, \mathcal{B})$ is a $t - (v, k, \lambda)$ block design (i.e. $|V| = v$, each block in $\mathcal{B}$ contains $k$ elements and each $t$-element ...
0
votes
1answer
60 views
following block design I am trying to determine if the design is a BIBD and if so, determine its parameters $v, b ,r, k,$ and $\lambda$.
For the following block design I am trying to determine if the design is a BIBD and if so, determine its parameters $v, b ,r, k,$ and $\lambda$. $$V = \{1,2,3,4\}$$ blocks: $\{1,4\}, \{3,4\}, \{2,3,4\}...
1
vote
1answer
28 views
What are the planes of $AG_2(2)$?
I am trying to understand the question (this is Van Lint's Intro to Combinatorics) by first looking at when $r=2$. The points are ordered pairs with each entry in $\mathbb{F}_2$ and all possible ...
1
vote
1answer
229 views
Construction to show that block design exists
I am taking a mathematics course and we covered block designs.
I have tried solving the following problem, but I can't find a final answer.
"Give an explicit construction to show that a block design ...
3
votes
1answer
49 views
Orbits and Stabilizers of a group that acts t-transitively.
Full question: Let $G$ be a group that acts $t$-transitively on a set $X$. Let $S$ be a $k$-subset of $X$. Show that the orbit $S^G$ of $S$ under the action of $G$ forms a $t-(n,k,\lambda)$-design ...
2
votes
1answer
221 views
Finite Incidence Geometry Questions
Definition of finite incidence geometry given: Consists of a finite set $P$ of points and a set of nonempty subsets of $P$ called lines, that satisfy the axioms:
(F1) Two points determine exactly one ...
1
vote
1answer
33 views
Prove that an $AG(2, n)$ is never a 3-design (except in the trivial case $n=2$).
My attempt:
Consider $AG(2,n)$ with $n\geq 3$. We know that $AG(2,n)$ is a BIBD with parameters $(n^2,n^2+n, n+1,n,1)$ $\implies$ $b=n^2+n$. But for any t-design, $b=$ $\lambda {v\choose t}\over {k \...
1
vote
1answer
54 views
Show that $t-(v,k,\lambda)$ design with $v\leq k+t$ is trivial
Let $D=(V,B)$ be a $t-(v,k,\lambda)$ design where $V$ is a finite set and $B$ is a collection of subsets of $V$. A trivial $t$-design is defined as a design with one block that contains all the points ...
1
vote
1answer
79 views
Prove that a Balanced Incomplete Block Design with parameters $(n^2, n^2+n, n+1, n, 1)$ is a finite Affine Plane
I know I need to show that those parameters imply that the following axioms hold when we consider treatments to be points and blocks to be lines:
A1: given any two points, there is one and only one ...
2
votes
1answer
83 views
Counting squares in finite fields (Paley Design)
Consider the following construction due to Paley: Let $q$ be a prime power congruent to 3 modulo 4, and let $Q \subset \mathbb{F}_q$ be the set of nonzero squares (note that $-1 \notin Q$). Call $X = \...
