16 votes
Accepted

Scrambling a “Connections” grid

Yes, here is one solution for the 4-by-4 case found by a computer search. Each array is obtained from the previous one by applying the permutation (0 1 2 3 4)(5 6 7 8 9)(10 11 12 13 14) to the entries....
Ed Kirkby's user avatar
  • 176
10 votes

Fano plane drawings: embedding PG(2,2) into the real plane

Here is a bit more symmetric version of the picture in the accepted answer:
Anton Petrunin's user avatar
9 votes

When do such regular set systems exist?

The answer to the first question is "no." Suppose $|M|=11$ and $\mathcal S\subset\binom M5$ and $|\mathcal S|=77.$ Since each $5$-set contains five $4$-sets, and since $77\cdot5=385\gt330=\binom{11}4,$...
bof's user avatar
  • 11.5k
9 votes
Accepted

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

I claim that $S_{k,n}=2^k$ for all $n\geqslant k$. Moreover, $\sum 2^{-m_i}\leqslant 1$ if the set of strings satisfies this condition, and $m_i$ denotes the number of zeros/ones in $i$-th string. ...
Fedor Petrov's user avatar
9 votes
Accepted

Is every uniform hyperbolic linear space infinite?

The answer is "No".There exist a finite plane with required property. First of all, let's rephrase your question. Your uniform linear space is a synonym to a BIBD (balanced incomplete block ...
Ihromant's user avatar
  • 471
8 votes

When do such regular set systems exist?

Switching to complements, the question is if we can choose 77 6-subsets of an 11-set $M$ such that any 5-subset of $M$ is contained in a chosen 6-subset (it is clear that this subset would be unique ...
Max Alekseyev's user avatar
8 votes

Seeking very regular $\mathbb Q$-acyclic complexes

Here's at least a couple of candidate designs which have the first four properties, although I haven't checked acyclicity and don't yet see how to exploit the existing symmetries to check it other ...
GNiklasch's user avatar
  • 2,391
7 votes

Latin squares with one cycle type?

There are also "pan-Hamiltonian" Latin squares, see Perfect Factorisations of Bipartite Graphs and Latin Squares Without Proper Subrectangles by I. M. Wanless, Electronic J. Combin. 6 (1999),...
Brendan McKay's user avatar
6 votes
Accepted

Minimum covers of complete graphs by $4$-cycles

If $n$ is odd, the answer is $\lceil \binom{n}{2}/4 \rceil$. If $n$ is even, the answer is $\lceil \binom{n}{2}/4+n/8 \rceil$. This follows from two special cases of a more general conjecture by ...
Tony Huynh's user avatar
  • 31.5k
6 votes

Status of Hadamard matrix conjecture

With all due respect to Colin McLarty, here is (in my not so humble opinion) a better answer. The conjecture (For every positive integer $k,$ there is a square matrix $H$ of order $4k$ such that $H$ ...
Gerhard Paseman's user avatar
6 votes

Best strategy for a combinatorial game

Let me address the case $k=N/2$. Consider a hypergraph whose edges are your groups. Then, basically, you are interested in the discrepancy of your hypergraph. The first estimate at the linked ...
Ilya Bogdanov's user avatar
6 votes
Accepted

Latin squares with one cycle type?

One way to achieve the required property is to construct a Latin square whose autotopism group acts transitively on unordered pairs of rows. This can be achieved for orders that are a prime power ...
Ian Wanless's user avatar
6 votes
Accepted

Smallest number of subsets whose squares cover the whole square

You are looking for $(n,k,2)$-covering designs, and your $f(k,n)$ is denoted $C(n,k,2)$. See https://www.dmgordon.org/cover/ For example, $f(3,6)=C(6,3,2)=6$: https://ljcr.dmgordon.org/show_cover.php?...
RobPratt's user avatar
  • 5,159
5 votes

Linear algebra proofs in combinatorics?

Here's a surprising use of inner product spaces in algebraic combinatorics. For $S,T\subseteq[n-1]$, let $$ \beta(S,T) := \#\{w\in \mathfrak{S}_n\colon D(w)=S, D(w^{-1})=T\},$$ where $D(w)$ is the ...
5 votes

Linear algebra proofs in combinatorics?

Linear algebra is also useful for proving lower bounds in extremal "bootstrap percolation" type problems. For example, Alon and Kalai used linear algebra (actually, exterior algebra) to (independently)...
5 votes

Best strategy for a combinatorial game

The question is a little ambiguous as to what it is asking. But the idea is clear and it is a nice question. As I interpret it, I think the answer might be no and that designs and finite geometries ...
Aaron Meyerowitz's user avatar
5 votes

What are efficient pooling designs for RT-PCR tests?

Let me get started with a small take at question 3, by proving that for $v\le 6$, the complete quadrilateral is optimal. First, for $v\in\{1,2,3\}$ it is clear that no pooling design can have ...
Benoît Kloeckner's user avatar
5 votes

What are efficient pooling designs for RT-PCR tests?

This isn't a full answer, but too long for a comment. I suppose it comes closest to trying to answer Question 3 or the general question of whether the hypercube design can be improved. Definition ...
Louis D's user avatar
  • 1,666
5 votes

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

It seemed to me that the commenters know much more about this problem than they write in the comments. For that reason alone I am posting this answer, which is most likely a long comment. For brevity, ...
kabenyuk's user avatar
  • 673
5 votes
Accepted

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

This is a previous comment which was moved to chat by Ben Webster: In fact for every prime $p$ if $A=[-(2m-1),-m] \cup [m, 2m-1]$ for $(p+3)/8\le m<(p+3)/6$, then $\mathbb Z/p\mathbb Z$ is a ...
Peter Mueller's user avatar
5 votes
Accepted

Construction of skew-Hadamard matrix of order 292

The skew Hadamard matrix of order 292 can be constructed from skew supplementary difference sets (kindly supplied to us by Prof. Djokovic). This same construction is used, for example, in Djokovic - ...
Matteo Cati's user avatar
5 votes
Accepted

Does every finite affine plane have the doubling property?

There is even stronger claim from which follows your answer. Claim. Any affine plane obtained from Veblen-Weddenburn projective plane by dropping one line don't have "doubling" property. ...
Ihromant's user avatar
  • 471
4 votes

On the Steiner system $S(4,5,11)$

This is not an answer, but a list containing the 66 blocks, as I've spent ages trying to find it online, without any success. I hope this will be useful in the future for people who look for it (like ...
domotorp's user avatar
  • 18.3k
4 votes
Accepted

reverse definition for magic square

This problem is so famous. For first trivial reference, you can see:link. $\it{R. Bodendiek}$ and $\it{G. Burosch}$ studied this problem in a paper with name: "Solution to the Antimagic 0,1,-1 ...
Shahrooz's user avatar
  • 4,746
4 votes

Status of Hadamard matrix conjecture

According to the current version on the MathWorld website by Wolfram, http://mathworld.wolfram.com/HadamardMatrix.html : "… the smallest unknown order [$of\ a\ possible\ Hadamard\ matrix$] is 668." ...
Wlodek Kuperberg's user avatar
4 votes
Accepted

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?

Take a 2-$(v,4,1)$ design on $v$ points and delete one block, along with the four points on it. In the original system each point is on exactly $(v-1)/3$ blocks, so if we assume $v\ge25$ the geometry ...
Chris Godsil's user avatar
4 votes

Self-complementary block designs

These are the parameters for Hadamard 2-designs. Let $H$ be an $n\times n$ Hadamard matrix, where $n=4m$, normalized so that all entries in the first row are equal to 1. Each row apart from the first ...
Chris Godsil's user avatar
4 votes

Constructing Group Divisible Designs - Algorithms?

There are some implementations available in sagemath, see e.g. http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/designs/group_divisible_designs.html#sage-combinat-designs-group-...
Dima Pasechnik's user avatar
4 votes

What are efficient pooling designs for RT-PCR tests?

If you are thinking about the realistic problem for COVID-19, then it is different from your mathematical question. I tried to make a summary about the real question: https://arxiv.org/pdf/2005.02388....
Endre Csóka's user avatar
4 votes
Accepted

Cycling through a general combinatorial design on $\omega$

If there are infinitely many blocks, then indeed you can find the permuations $\pi_n$ as desired. Indeed, there are computable such $\pi_n$. Furthermore, you don't need that every block has size at ...
Joel David Hamkins's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible