All Questions

Filter by
Sorted by
Tagged with
3 votes
0 answers
39 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
  • 441
5 votes
5 answers
495 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
  • 40.2k
11 votes
1 answer
295 views

Has every finite affine plane 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
  • 40.2k
1 vote
1 answer
68 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
125 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
  • 344
1 vote
0 answers
80 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
  • 2,874
1 vote
1 answer
123 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
11 votes
2 answers
652 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.6k
1 vote
1 answer
134 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
  • 25
5 votes
0 answers
881 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
  • 3,997
8 votes
3 answers
411 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
3 votes
0 answers
51 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.1k
3 votes
0 answers
132 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
663 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
48 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
190 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
  • 479
11 votes
5 answers
489 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
134 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
  • 645
4 votes
3 answers
232 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
  • 381
5 votes
2 answers
191 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
352 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
  • 598
2 votes
1 answer
59 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
84 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
117 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
  • 21.7k
2 votes
1 answer
128 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,282
8 votes
2 answers
549 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,100
2 votes
1 answer
207 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
0 votes
0 answers
90 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
697 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,626
2 votes
0 answers
193 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}$ ...
H A Helfgott's user avatar
  • 19.1k
3 votes
0 answers
91 views

what is the largest real orthogonal design in $n$ variables?

A real orthogonal design in $n$ variables is an $m \times n$ matrix with entries from the set $\pm x_1,\pm x_2,\cdots,\pm x_n$ that satisfies : $$ A A^T = (x_1^2 + x_2^2 + \cdots x_n^2) I_m $$ ...
unknown's user avatar
  • 451
10 votes
2 answers
618 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 $...
Gil Kalai's user avatar
  • 24.1k
7 votes
0 answers
205 views

More about self-complementary block designs

For what odd integers $n \geq 3$ does there exist a self-complementary $(2n,8n−4,4n−2,n,2n−2)$ balanced incomplete block design? By "self-complementary" I mean that the complement of each block is a ...
James Propp's user avatar
  • 19.1k
2 votes
2 answers
211 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 \} = \...
Lior's user avatar
  • 21
7 votes
2 answers
295 views

Self-complementary block designs

For what $n$ does there exist a self-complementary $(2n,4n-2,2n-1,n,n-1)$ balanced incomplete block design? (All I know is that a self-complementary design with these parameters does exist for all $...
James Propp's user avatar
  • 19.1k
1 vote
1 answer
298 views

Covering designs where $v$ is linear in $k$

A $(v,k,t)$ covering design is a collection of $k$-subsets of $V=\{1,\ldots,v\}$ chosen so that any $t$-subset of $V$ is contained in (or "covered by") at least one $k$-set in the collection. ...
Robert Bailey's user avatar
3 votes
2 answers
304 views

When do such regular set systems exist?

Let '$n$-set' mean 'a set with $n$ elements'. May we choose $77=\frac16\binom{11}5$ 5-subsets of 11-set $M$ such that any 6-subset $A\subset M$ contains unique chosen subset? Positive answer to ...
Fedor Petrov's user avatar
5 votes
1 answer
453 views

reverse definition for magic square

Recently, I saw a question in see here which is so interesting for me. This question is as follows: Is it possible to fill the $121$ entries in an $11×11$ square with the values $0,+1,−1$, so that ...
Meysam Ghahramani's user avatar
7 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 ...
kodlu's user avatar
  • 9,818
0 votes
1 answer
49 views

Vector version of balanced incomplete block designs

I am interested in finding out what is known about the following generalization of balanced incomplete block designs (BIBDs): "What is the maximum size of a collection $B$ of $v$-dimensional unit ...
Rasmus Pagh's user avatar
4 votes
0 answers
344 views

Existence of a block design

Let $\ell$ be an integer parameter. I want to ask the existence of the following design: There is a universal constant $\beta < 1$ such that for all sufficiently large $\ell$, the following holds: ...
Xi Wu's user avatar
  • 143
3 votes
0 answers
121 views

A question on the behavior of intersections of certain block design

Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that: $\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$. $\forall i \neq j \in [m]$, $|S_i \cap S_j| \...
Xi Wu's user avatar
  • 143
2 votes
1 answer
302 views

Existence of Steiner system designs given $n,k,t$

I am familiar with the recent Keevash paper here which proves that given some $t,n,k,\lambda$ then provided standard divisibility conditions hold, and $n$ is suitably large, there exists a $t-(n,k,\...
Baron Crinkle's user avatar
6 votes
2 answers
1k views

Combinatorial designs textbook recommendation

Good evening, I am currently taking a class which has combinatorial designs as the first topic, we are using Peter Cameron's book Designs, Graphs, Codes and their Links which I am finding extremely ...
Gorka's user avatar
  • 1,825
2 votes
2 answers
762 views

Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets: Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...
Jim's user avatar
  • 145
4 votes
2 answers
568 views

covering designs of the form $(v,k,2)$

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is ...
Gorka's user avatar
  • 1,825
39 votes
2 answers
1k views

How close can one get to the missing finite projective planes?

This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...
Gjergji Zaimi's user avatar
4 votes
0 answers
170 views

Reduction argument from a general vertex set V(G) to a prime power in Prof. Keevash's proof on the Existence of Designs

The proof flow of the paper "On the Existence of Designs" by Prof. Keevash as I understand it is the following: -- Reduction from the general case to $V = \mathbb{F}_{p^a}$ (Lemma 6.3) -- Covering ...
Sankeerth's user avatar