Skip to main content

Questions tagged [combinatorial-designs]

Design theory is the subfield of combinatorics concerning the existence and construction of highly symmetric arrangements. Finite projective planes, latin squares, and Steiner triple systems are examples of designs.

Filter by
Sorted by
Tagged with
6 votes
0 answers
72 views

What is the largest subgraph of the Kneser graph which has a small chromatic number?

While trying to characterize constraint satisfaction problems which can be solved by the Linear Programming relaxation, I've run into a few perplexing puzzles related to the existence of certain ...
zeb's user avatar
  • 8,623
15 votes
1 answer
875 views

Scrambling a “Connections” grid

Given a 4-by-4 array of distinct words, is it possible to scramble the array in four different ways in such a fashion that each possible word-pair appears adjacently in one of the five arrays (the ...
James Propp's user avatar
  • 19.5k
3 votes
1 answer
288 views

Smallest number of subsets whose squares cover the whole square

Let $2 \leq k \leq n$ be integers, let $[n] := \{1,2,\ldots,n\}$, and for a subset $A \subseteq [n]$ let $A^2 := A \times A$ be the Cartesian product of $A$ with itself and let $|A|$ denote the ...
Nathaniel Johnston's user avatar
4 votes
0 answers
77 views

Software reference for combinatorial design

If one were to require quick and easy access to sizeable latin squares, room squares, Steiner systems, designs, balanced block designs... where to look, what software to use?
5th decile's user avatar
  • 1,451
4 votes
0 answers
59 views

Existence of finite 3-dimensional hyperbolic balanced geometry

Together with @TarasBanakh we faced the problem described in the title. Let me start with definitions. A linear space is a pair $(S,\mathcal L)$ consisting of a set $S$ and a family $\mathcal L$ of ...
Ihromant's user avatar
  • 471
0 votes
0 answers
40 views

Minimal m such that m x K_n is decomposable into disjoint C_3

For a given $n$, is there a way to calculate the minimal value $m$ such that you can decompose the multigraph: $$m \times K_n$$ into disjoint 3-cycles? What about a more general result applied to ...
Sebastian's user avatar
  • 101
2 votes
2 answers
307 views

A graphic representation of classical unitals on 28 points

I would like to understand the geometry of the classical unitals. They are block designs containing $q^3+1$ points and whose blocks have cardinality $q+1$, where $q$ is a prime power. For $q=2$ (if I ...
Taras Banakh's user avatar
5 votes
5 answers
552 views

Is every uniform hyperbolic linear space infinite?

I start with definitions. Definition 1. A linear space is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ satisfying three axioms: (L1) for any distinct ...
Taras Banakh's user avatar
11 votes
1 answer
375 views

Does every finite affine plane have the doubling property?

Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms: Any distinct points $x,y\...
Taras Banakh's user avatar
1 vote
1 answer
76 views

One question about nega-cyclic Hadamard matrices

Let $n$ be a multiple of $4$, is there any $n \times n$ negacyclic Hadamard matrix? If yes - how to construct it? If no - why? Here an $n \times n$ nega-cyclic matrix is a square matrix of the form: \...
user369335's user avatar
3 votes
1 answer
130 views

On the half-skew-centrosymmetric Hadamard matrices

Definition 1: A Hadamard matrix is an $n\times n$ matrix $H$ whose entries are either $1$ or $-1$ and whose rows are mutually orthogonal. Definition 2: A matrix $A$ is half-skew-centrosymmetric if ...
user369335's user avatar
0 votes
1 answer
157 views

"JigSaw Puzzle" on Set Family

One of my research problem can be reduced to a question of the following form Given a set family $\mathcal{F}$ of $[n]$ , such that every element of $[n]$ lies in exactly $K$ sets in $\mathcal{F}$, ...
abacaba's user avatar
  • 364
0 votes
0 answers
81 views

Bounds for smallest non-trivial designs

Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...
Zach Hunter's user avatar
  • 3,413
1 vote
1 answer
132 views

On the existence of symmetric matrices with prescribed number of 1's on each row

We are considering the following problem: Given an integer $n$ and a sequence of integers $r_i,\ 1\le i\le n$, with $0\le r_i\le n-1$ does there exists a symmetric matrix $A$ such that the diagonal ...
Jeremiah's user avatar
6 votes
1 answer
144 views

How to construct a skew Hadamard matrix of order 756?

Where can I find the construction for a skew Hadamard matrix of order 756? According to multiple papers (e.g. Koukouvinos and Stylianou - On skew-Hadamard matrices and Seberry - On skew Hadamard ...
Matteo Cati's user avatar
9 votes
1 answer
305 views

Construction of skew-Hadamard matrix of order 292

I am currently looking into how to construct a skew-Hadamard matrix of order 292. Where can I find such construction? According to multiple papers (e.g. Koukouvinos and Stylianou - On skew-Hadamard ...
Matteo Cati's user avatar
11 votes
2 answers
658 views

$\mathbb Z/p\mathbb Z=A\cup(A-A)$?

$\newcommand{\Z}{\mathbb Z/p\mathbb Z}$ Can one partition a group of prime order as $A\cup(A-A)$ where $A$ is a subset of the group, $A-A$ is the set of all differences $a'-a''$ with $a',a''\in A$, ...
Seva's user avatar
  • 22.8k
3 votes
1 answer
150 views

Cycling through a general combinatorial design on $\omega$

This is a generalisation of an older question inspired by a football tournament (which does not have an answer yet). Let $\frak P$ be a partition of $\omega$ into blocks, that is, pairwise disjoint ...
Dominic van der Zypen's user avatar
1 vote
0 answers
101 views

On a combinatorial design inspired by a football (soccer) tournament

Real-world inspiration. My younger son was playing a micro football (soccer) tournament this afternoon with $3$ other friends. Let's label the $4$ kids $0,1,2,3$. They played $3$ matches: $\{0,1\} \...
Dominic van der Zypen's user avatar
1 vote
1 answer
136 views

3-partition of a special set

$S_5$ is a set consisting of the following 5-length sequences $s$: (1) each digit of $s$ is $a$, $b$, or $c$; (2) $s$ has and only has one digit that is $c$. $T_5$ is a set consisting of the following ...
4869's user avatar
  • 47
5 votes
0 answers
889 views

The existence of big incompatible families of weight supports

In 2018 Mario Krenn posed this originated from recent advances in quantum physics question on a maximum number of colors of a monochromatic graph with $n$ vertices. Despite very intensive Krenn’s ...
Alex Ravsky's user avatar
  • 4,112
8 votes
3 answers
421 views

Latin squares with one cycle type?

Cross posting from MSE, where this question received no answers. The following Latin square $$\begin{bmatrix} 1&2&3&4&5&6&7&8\\ 2&1&4&5&6&7&8&3\\...
user1020406's user avatar
4 votes
1 answer
80 views

k-partite design

Is the following true? For every $n \geq 1, k\geq 2$, there is a set $S \subseteq [n]^k$ of size $|S| = n^2$ such that every two $k$-tuples in $S$ have at most one common entry. Does anyone know if ...
Lior Gishboliner's user avatar
1 vote
0 answers
55 views

Are sharper lower bounds known for these potentials on the sphere?

Fix a positive integer $\ell$. For $x_1,\dotsc,x_n\in S^{d-1}$, Venkov proved that $$ \sum_{i=1}^n\sum_{j=1}^n(x_i\cdot x_j)^{2\ell}\geq\frac{(2\ell-1)!!(d-2)!!}{(d+2\ell-2)!!}\cdot n^2, $$ with ...
Dustin G. Mixon's user avatar
3 votes
0 answers
53 views

Cliques in Incomplete block designs

I'm interested in inequalities that guarantee the presence of cliques in incomplete block designs. Here's the set-up: I have an incidence structure $(V, B)$ which is an incomplete block design: $V$ is ...
Nick Gill's user avatar
  • 11.2k
3 votes
0 answers
135 views

Linear combinations of special matrices

I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm. Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
BenBar's user avatar
  • 73
4 votes
3 answers
732 views

Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
Yungchen Jen's user avatar
1 vote
0 answers
51 views

Optimal choice of points to maximize majorities in a $t-(v,k,\lambda)$ design

Let us consider a design $\mathcal{D} = (V,\mathcal{B})$ with points in $V$ and blocks in $\mathcal{B}$. I am interested in the special case of a $t-(v,k,\lambda)$ design for $k=3$, i.e., all blocks ...
mgus's user avatar
  • 143
12 votes
1 answer
193 views

Ternary sequences satisfying $ x_i + y_i = 1 $ for some $ i $

Consider a set of strings $ {\mathcal S} \subset \{0, 1, 2\}^n $ satisfying the following two conditions: 1.) every string in $ {\mathcal S} $ has exactly $ k $ symbols from $ \{0, 1\} $ (i.e., $ \...
aleph's user avatar
  • 503
11 votes
5 answers
494 views

What are efficient pooling designs for RT-PCR tests?

I realize this is long, but hopefully I think it may be worth the reading for people interested in combinatorics and it might prove important to Covid-19 testing. Slightly reduced in edit. The ...
Benoît Kloeckner's user avatar
3 votes
1 answer
141 views

Mutually orthogonal Latin hypercubes

A $d$-dimensional Latin hypercube with side length $n$ is a $d$-dimensional array with $n$ symbols such that along any line parallel to an axis, each symbol appears exactly once. Let us call a $(n,d)$ ...
BPP's user avatar
  • 665
3 votes
1 answer
75 views

For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?

Or, equivalently - for what sets of $(n, m, k)$ is it possible, for a group* of $n$ people, to arrange $k$ days of "meetings", such that every day the group is split into subgroups of $m$ people, and ...
scubbo's user avatar
  • 131
1 vote
1 answer
67 views

Does there exist a non-degenerate symmetric combinatorial 3-design?

Is there a non-degenerate 3-design where the number of blocks equals the number of points? Non-degenerate in this context means that a point is incident with at least 2 and at most #blocks-2 blocks.
Souri's user avatar
  • 11
2 votes
0 answers
83 views

Packings with block size equal to $6$?

In design theory the following is the defintion of a packing : Definition : A $(v,k)$-packing is a pair $(V, \mathcal{B})$ of a finite set $V$ of cardinality $\vert V \vert = v$ and a finite set $\...
Elaqqad's user avatar
  • 203
4 votes
3 answers
235 views

Best strategy for a combinatorial game

Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball. Now suppose we are given 5 chances to pick 20 out of ...
Magi's user avatar
  • 281
5 votes
2 answers
199 views

Coloring in Combinatorial Design Generalizing Latin Square

I have a question about a combinatorial design very similar to a Latin Square, which is arising out of an open problem in graph theory. The design is an $n \times n$ matrix whose entries we want to ...
John Samples's user avatar
3 votes
0 answers
129 views

Graeco-Latin squares and outer-automorphisms

It is well known that $n=6$ is the only number greater than two in which there is no Graeco-Latin square of order $n$. It is also well known that $n=6$ is the only number greater than two in which ...
Craig Feinstein's user avatar
10 votes
2 answers
359 views

Lower bound for a combinatorial problem ($N$ students taking $n$ exams)

We have $N$ students and $n$ exams. We need to select $n$ out of the students using the grade of those exams. The procedure is as follows: 1- We set some ordering on the exams. 2- Going through this ...
Morteza's user avatar
  • 628
2 votes
1 answer
60 views

Constructing Group Divisible Designs - Algorithms?

I am starting my research on group divisible designs this year and I wonder if there are any algorithms/software that help with constructions. Thank you
Jake's user avatar
  • 29
4 votes
1 answer
99 views

Bounding the number of orthogonal Latin squares from above

As is usual, let $N(n)$ denote the maximum size of a set of mutually orthogonal Latin squares of order $n$. I am wondering what results hold that bound $N(n)$ from above; the only ones I can think of ...
Nathaniel Butler's user avatar
3 votes
1 answer
120 views

On the existence of a certain graph/hypergraph pair

Let $V$ be a finite set, $G$ a simple graph with vertex set $V$, and $H$ a hypergraph (i.e., set of subsets) with vertex set $V$ satisfying the following three conditions: each pair of elements of $V$...
Sam Hopkins's user avatar
2 votes
1 answer
130 views

Distinguishing points by sets of given size

The problem is: Given a finite set $X$ with size $x$ and let $B$ denote a family of $k$-element subsets of $X$, called blocks. What is the smallest possible number $n$ of blocks such that every ...
LeechLattice's user avatar
  • 9,421
8 votes
2 answers
566 views

Pfaffian representation of the Fermat quintic

It is known (see for instance Beauville - Determinantal hypersurfaces) that a generic homogeneous polynomial in $5$ variables of degree $5$ with complex coefficients can be written as the Pfaffian of ...
Libli's user avatar
  • 7,240
4 votes
2 answers
251 views

Known result about existence of $n$-vertex $k$-uniform $r$-hypergraphs?

Are there known results about $n,k,r$ such that $n$-vertex $k$-uniform $r$-regular hypergraphs exist? If this is too large a class of hypergraphs, what if $k=\tilde{\theta}(\sqrt{n})$? What if an ...
Connor's user avatar
  • 251
7 votes
2 answers
391 views

Minimum covers of complete graphs by $4$-cycles

I am interested in coverings of the (edge set of the) complete graph $K_n$ by cycles of length $4$. It is clear that such coverings exist for each $n \ge 4$. I need to find the minimum number of $4$-...
Ashot's user avatar
  • 337
2 votes
1 answer
99 views

Relative difference sets?

Do you know how to find order of known groups with RDS or without? Or Known groups which have RDS or not? If there is a references to survey all researches?
user avatar
2 votes
1 answer
215 views

Has this kind of design been studied before?

Consider a design $(X,\mathcal{B})$, satisfying: Each block in $\mathcal{B}$ has the same size The intersection of every two blocks has the same size Of course, it is easy to find many examples of ...
smart cat's user avatar
2 votes
0 answers
82 views

A generalization of PBIBDs

A PBIBD is an incidence structure together with an underlying symmetric association scheme. One can relax the symmetry requirement, and ask for incidence structures with an underlying (not necessarily ...
DKal's user avatar
  • 151
0 votes
0 answers
91 views

Steiner-like systems with large edges and many intersections

Let $l\geq 3$ be an integer. Is there $n\in\mathbb{N}$ and a hypergraph $H=(\{1,\ldots,n\},E)$ with the following properties? for all $e\in E$ we have $|e| \geq l$ $e_1\neq e_2 \in E \implies |e_1 \...
Dominic van der Zypen's user avatar
4 votes
3 answers
741 views

Does there exist a finite hyperbolic geometry in which every line contains at least 3 points, but not every line contains the same number of points?

It seems to me that the answer should be yes, but my naive attempts to come up with an example have failed. Just to clarify, by finite hyperbolic geometry I mean a finite set of points and lines such ...
Louis D's user avatar
  • 1,676