# 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.

121 questions
Filter by
Sorted by
Tagged with
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 ...
• 8,623
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 ...
• 19.5k
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 ...
• 5,765
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?
• 1,451
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 ...
• 471
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 ...
• 101
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 ...
• 41k
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 ...
• 41k
375 views

1 vote
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 ...
• 47
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 ...
• 4,112
421 views

• 7,583
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 ...
• 11.2k
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 ...
• 73
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 ...
1 vote
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 ...
• 143
193 views

• 203
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 ...
• 281
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 ...
• 409
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 ...
• 2,549
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 ...
• 628
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
• 29
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 ...
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$...
• 23k
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 ...
• 9,421
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 ...
• 7,240
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 ...
• 251
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$-...
• 337
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?
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 ...
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 ...
• 151
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 \...