All Questions
Tagged with combinatorial-designs co.combinatorics
100 questions
0
votes
1
answer
118
views
Configurations of signs in a matrix under certain conditions
I have a combinatorial question which is out of my research area.
Given a $2^k\times 2^k$ matrix $A=[a_{i,j}]$ with entries in $\lbrace0,\pm1\rbrace$, where $k$ is a positive integer. Is it possible ...
- 619
2
votes
0
answers
187
views
Matrix with elementary symmetric polynomials as entries
Let $n\geq 1$, and for each $j=1,\ldots, n+1$ let $\mathbf{X}_{j}=(X_{j1},\ldots, X_{jn})$ be $n$ variables. Let $M$ be the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $$M_{ij}=(-1)^i e_{i-1}(...
4
votes
1
answer
170
views
About $CW(512,16^2)$
Definitions: A weighing matrix $W = W(n,k)$ with weight $k$ is a square matrix of order $n$ and entries $w_{ij}$ in $\{0, \pm 1\}$ such that $WW^T=kI$,
where $I$ is the identity matrix. A circulant ...
- 1,021
5
votes
2
answers
189
views
Bisymmetric Hadamard matrices
Definitions: An $n\times n$ Hadamard matrix is a matrix whose entries are either $1$ or $−1$ and whose rows are mutually orthogonal.
A symmetric matrix is a square matrix that is equal to its own ...
- 696
3
votes
0
answers
317
views
Prime Hadamard matrices
Assume that $n$ is a sufficiently large number. Is there a Hadamard matrix $H_{4n \times 4n}=(h_{ij})$ with the last row and the last cloumn $J$ (thet is, for every $k$, $h_{k,4n}=1$ and $h_{4n, k}=1$)...
- 696
6
votes
0
answers
111
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,688
11
votes
1
answer
390
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\...
- 63.9k
5
votes
5
answers
572
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 ...
- 41.8k
4
votes
0
answers
77
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 ...
- 501
15
votes
1
answer
886
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 ...
- 176
3
votes
1
answer
294
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 ...
- 6,351
4
votes
0
answers
89
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,461
8
votes
1
answer
1k
views
Are there infinite constructions for partial circulant Hadamard matrices?
I believe that the circulant Hadamard conjecture (that there are no circulant Hadamard matrices of size greater than $4\times4$) is still open.
I also know that examples of $(n/2) \times n$ matrices ...
56
votes
21
answers
14k
views
Linear algebra proofs in combinatorics?
Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
- 5,822
11
votes
2
answers
856
views
On the Steiner system $S(4,5,11)$
Is there a nice way to partition the edges of the complete $5$-uniform hypergraph
on $11$ vertices into $7$ copies of the Steiner system $S(4,5,11)$? If this is
obvious or elementary, I apologize in ...
- 63.9k
2
votes
1
answer
98
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:
\...
- 34.3k
5
votes
1
answer
141
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 ...
- 1,245
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}$, ...
- 384
0
votes
0
answers
84
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 ...
- 3,499
1
vote
1
answer
136
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 ...
- 34.3k
6
votes
0
answers
4k
views
A generalization of covering designs and lottery wheels
This question is inspired by a recent problem . A $(v,k,t)$ covering design is a pair $(V,B)$ where $V$ is a set of $v$ points and $B$ is a family of $k$ point subsets (called blocks) such that ...
- 1
11
votes
2
answers
661
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$, ...
- 22.5k
5
votes
0
answers
911
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 ...
- 5,409
2
votes
2
answers
217
views
Minimal number of blocks in a $(n,n/2,\lambda)$ block design
A $(n,n/2,\lambda)$ block-design is a family $A_1,...,A_K$ of subsets of $[n]$ such that $|A_i|=n/2$ and for every $1 \leq i < j \leq n$ it holds that
$\#\{1 \leq k \leq K : i,j \in A_k \} = \...
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 ...
- 5,429
4
votes
3
answers
780
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 ...
- 4,219
8
votes
3
answers
433
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\\...
3
votes
0
answers
148
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 ...
- 34.3k
3
votes
1
answer
150
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)$ ...
- 7,226
3
votes
0
answers
54
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
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 ...
- 143
11
votes
5
answers
506
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 ...
- 14.4k
12
votes
1
answer
194
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., $ \...
- 109k
4
votes
3
answers
240
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 ...
- 30.1k
5
votes
2
answers
211
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 ...
- 1,327
8
votes
2
answers
577
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,300
3
votes
0
answers
130
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,649
10
votes
2
answers
362
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 ...
CommunityBot
- 1
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
- 14k
4
votes
1
answer
113
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 ...
- 188k
11
votes
4
answers
5k
views
Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices
What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$?
If there's no exact formula what are the nearest upper and lower bounds do you know?
- 63.9k
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$...
- 23.7k
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 ...
CommunityBot
- 1
4
votes
1
answer
70
views
Balancing out edge multiplicites in a graph
Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge).
Is there some simple graph $H$ such that the $t$-fold ...
CommunityBot
- 1
10
votes
2
answers
632
views
Seeking very regular $\mathbb Q$-acyclic complexes
This question was raised from a project with Nati Linial and Yuval Peled
We are seeking a $3$-dimensional simplicial complex $K$ on $12$ vertices with the following properties
a) $K$ has a complete $...
- 2,391
3
votes
1
answer
222
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 ...
CommunityBot
- 1
4
votes
1
answer
1k
views
"Codes" in which a group of words are pairwise different at a certain position
I read the following problem, claimed to be in the IMO shortlist in 1988:
A test consists of four multiple choice problems, each with three options, and the students should give an unique answer to ...
- 103
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 \...
- 48.9k
4
votes
3
answers
781
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 ...
CommunityBot
- 1
2
votes
0
answers
204
views
Non-uniform Ray-Chaudhuri-Wilson (generalized Fisher's inequality)
A $t$-design on $v$ points with block size and index $\lambda$ is a collection $\mathcal{B}$ of subsets of a set $V$ with $v$ elements satisfying the following properties:
(a) every $B\in\mathcal{B}$ ...
- 20.2k