Zarankiewicz's problem

[Freywa]

All non-isomorphic solutions to certain small square instances of the 3×3 and 4×4 Zarankiewicz's problem, as verified through SAT solving:

Code: Select all

x = 176, y = 184, rule = LifeHistory
21.D5.3D4.3D5.D.3D4.D.3D5.3D.3D4.3D.3D5.D.D.3D6.3D.3D7.3D.D.D8.3D.3D
9.3D.D12.D.3D.3D$21.D7.D4.D7.D.D.D4.D.D9.D3.D6.D3.D5.D.D.D.D6.D5.D7.D
3.D.D10.D3.D9.D.D.D12.D.D.D.D$21.D5.3D4.3D5.D.D.D4.D.3D5.3D.3D4.3D.3D
5.3D.D.D6.3D.3D7.3D.3D10.D3.D9.3D.D12.D.D.D.3D$21.D7.D6.D5.D.D.D4.D.D
.D5.D3.D8.D.D9.D.D.D8.D.D9.D.D3.D10.D3.D11.D.D12.D.D.D3.D$21.D5.3D4.
3D5.D.3D4.D.3D5.3D.3D4.3D.3D7.D.3D6.3D.3D7.3D3.D10.D3.D9.3D.D12.D.3D.
3D2$3D5.3D10.5D.6D.7D.8D.9D.10D.11D.12D.13D.14D.15D.16D.17D$2.D.D.D3.
D10.DA2.D.DA3.D.DA4.D.DA5.D.D2.2A3.D.D2.A.2A2.D.D.2A6.D.D2A2.2A4.D.D
2.2A4.2A.D.DA4.2A4.AD.D2.A4.4A2.D.D4.3A4.3AD.D8.7AD$3D2.D2.3D10.D3.D.
D.A2.D.D.A3.D.D.2A3.D.D.A2.A2.D.D3.A.2A.D.DA2.2A4.D.D3A3.A3.D.D.A4.2A
.A.D.D3.2A.A2.2A.D.D2.5A6.D.D2.2A2.A2.2A2.AD.D4.4A4.3AD$2.D.D.D3.D10.
D3.D.D2.A.D.D2.A2.D.D.A.A2.D.DA4.A.D.DA3.A.A.D.DA4.2A2.D.D.3A3.A2.D.D
A2.A.A.A3.D.D3.3A.2A3.D.D3A8.2AD.D.A.A.A2.A.A.A.D.D2.2A2.2A2.2A2.AD$
3D5.3D10.5D.D4.D.D3.A.D.D2.A.A.D.DA2.2A2.D.D2A3.A2.D.D.A2.A.2A.D.D2.
3A3.A.D.DA.A.A.A4.D.D.2A3.3A3.D.D.A3.2A2.2A.AD.D.2A.A3.2A.A2.D.D2.4A
2.2A4.AD$27.6D.D4.AD.D3.2A.D.D.A.A.A.D.D.2A3.A.D.D.A.A.A.A.D.DA2.2A4.
AD.D3.A.2A.A.AD.D.2A2.A3.2A.D.D.A2.A.A.A.2A.D.DA2.2A2.A2.2A2.D.D.A.A.
A.A.A.A.A.D$34.7D.D5.AD.D2.A.2A.D.DA.2A4.D.D2.A.2A2.AD.DA4.A.2A.D.D2.
A.A2.2A.AD.DA.A.A3.A.A.D.D.A.A.A.A.A.A.D.DA.A2.A.A.A2.A.D.D.A.2A.A.A.
A2.A.D$42.8D.D6.AD.D.A.2A3.D.D2.2A2.A.AD.D.A4.A.2AD.D.A.2A.A3.AD.D2A.
A3.A.A2.D.D.A.2A2.2A3.AD.D2A4.3A4.AD.D.2A2.2A.A2.2A2.D$51.9D.D7.AD.D
3.2A2.2AD.D2.A2.A.A.AD.D.2A2.A.A2.AD.D2.2A2.2A2.2AD.DA4.4A2.A.D.D4.7A
3.D.D.2A.A2.A.2A.A2.D$61.10D.D5.4AD.D3.A.2A.A.D.DA3.2A3.2AD.D2.2A.A2.
2A.AD.DA3.A.2A.A2.AD.D2.2A2.3A2.2A.D.DA2.A.2A2.2A.A2.D$72.11D.D4.A.2A
.AD.D2A6.3AD.D.A2.A.A.2A.AD.DA2.A.A2.A.A.AD.D.A.A.A.A.A.A.AD.DA2.2A2.
2A2.2A2.D$72.D2A7.D.12D.D4.6A.D.D.A2.2A.A2.2AD.DA2.2A4.3A.D.D.2A.A2.A
2.A.2AD.DA.A2.A.2A.A2.A.D$72.DA4.4AD14.13D.DA6.5AD.D2.A.2A.A2.3AD.DA
2.2A3.2A2.2AD.DA.A.A.A2.A.A.A.D$72.D4.3A2.D28.14D.D2.2A2.A.2A.2AD.DA.
A2.A2.A.2A.AD.D2A4.4A4.AD$72.D3.A.A.A.D28.D.4A3.A3.D.15D.D2A4.A2.4A.D
.D2A2.2A4.2A2.AD$72.D2.A2.A2.AD28.DA.2A.A3.A2.D17.16D.D4A8.3AD$72.D.
4A4.D28.D2A.A2.A3.A.D34.17D$72.D.2A3.2A.D28.D3A4.A3.AD$72.D.A.A2.A.AD
28.DA3.5A3.D$72.D.A2.A2.2AD28.D.A2.4A.A2.D$72.11D28.D2.A.4A2.A.D$72.D
A7.AD28.D3.5A3.AD$72.D.A2.A2.A.D28.DA3.A4.3AD$72.D2.A.A.A2.D28.D.A3.A
2.A.2AD$72.D3.3A3.D28.D2.A3.A.2A.AD$72.D4A5.D28.D3.A3.4A.D$72.D3.A2.
3AD28.14D$72.D2.A2.A.2AD$72.D.A3.2A.AD$72.DA3.4A.D$72.11D$72.D2.2A4.A
D$72.D.A.A3.A.D$72.DA.A3.A2.D$72.D2A3.A3.D$72.D5.4AD$72.D3.4A2.D$72.D
2.A.2A.A.D$72.D.A2.A.A.AD$72.DA3.A2.2AD$72.11D$72.DA.A.A4.D$72.D.A3.
2A2.D$72.DA5.2A.D$72.D3.A3.2AD$72.DA3.2A2.AD$72.D.A2.A2.2AD$72.D.2A3.
A.AD$72.D2.2A.A.A.D$72.D3.4A2.D$72.11D$72.DA3.A3.AD$72.D.A2.A2.A.D$
72.D2.A.A.A2.D$72.D3.3A3.D$72.D4A5.D$72.D3.A2.3AD$72.D2.A2.A.2AD$72.D
.A3.2A.AD$72.DA4.3A.D$72.11D$72.DA3.A3.AD$72.D.A2.A2.A.D$72.D2.A.A.A
2.D$72.D3.3A3.D$72.D4A5.D$72.D2.2A3.2AD$72.D.A.A2.A.AD$72.DA.A2.A.A.D
$72.D2A3.2A2.D$72.11D11$21.D6.3D5.3D6.3D7.D.3D6.3D.3D5.3D.3D6.3D.3D7.
D.D.D.D8.3D.3D$21.D8.D5.D10.D7.D3.D8.D.D.D7.D.D10.D.D9.D.D.D.D8.D5.D$
21.D6.3D5.3D8.D7.D.3D6.3D.D.D5.3D.3D6.3D.3D7.3D.3D8.3D.3D$21.D8.D7.D
8.D7.D3.D6.D3.D.D5.D3.D.D8.D3.D9.D3.D10.D.D$21.D6.3D5.3D8.D7.D.3D6.3D
.3D5.3D.3D6.3D.3D9.D3.D8.3D.3D2$D.D5.D.D10.6D.7D.8D.9D.10D.11D.12D.
13D.14D.15D$D.D.D.D.D.D10.DA3.D.DA4.D.DA5.D.DA6.D.DA7.D.D.A7.D.D.A8.D
.DA10.D.DA11.D.D5.2A2.A.A.D$3D2.D2.3D10.D4.D.D.A3.D.D.A4.D.D.A5.D.D.A
6.D.DA8.D.DA9.D.D.2A8.D.D3.A2.A2.A2.D.D4.2A2.A.A2.D$2.D.D.D3.D10.D4.D
.D2.A2.D.D2.A3.D.D2.A4.D.D2.A5.D.D7.2AD.D6.A.2AD.D3.2A5.AD.D2.A.A3.A
3.D.D3.2A2.A.A3.D$2.D7.D10.D4.D.D5.D.D3.A2.D.D3.A3.D.D5.2A.D.D4.A.A2.
D.D5.A.2A.D.D3.A.A3.A.D.D.A3.A.A4.D.D2.2A2.A.A4.D$21.6D.D5.D.D4.A.D.D
4.A2.D.D6.2AD.D3.A.A3.D.D4.A.2A2.D.D4.A.A.A2.D.D2.A3.2A3.AD.D.2A2.A.A
5.D$28.7D.D6.D.D5.A.D.D3.A3.AD.D4.2A2.AD.D3.A.2A3.D.D5.3A3.D.D3.A.A2.
A2.AD.D2A2.A.A6.D$36.8D.D6.AD.D3.2A3.D.D3.A2.2A.D.D2.A.2A4.D.D.A4.A2.
2AD.D.A2.A4.A.AD.DA2.A.A6.AD$45.9D.D4.2A2.D.D2.A3.2A.D.D3.2A4.AD.D2.A
2.A2.A.AD.D3.2A2.A2.A.D.D2.A.A6.2AD$55.10D.D2.A2.A2.AD.D2.2A4.A.D.D2.
A.A2.A.A.D.D2.A2.A3.2A.D.D.A.A6.2A.D$66.11D.D2.A4.A.AD.D.A.A3.2A2.D.D
.A4.A.A.A.D.DA.A6.2A2.D$66.D.A7.D.12D.D7.4AD.D7.5AD.D.A6.2A2.AD$66.DA
8.D14.13D.D4.3A3.2AD.DA6.2A2.A.D$66.D7.2AD14.DA10.D.14D.D6.2A2.A.AD$
66.D4.A.A2.D14.D.A.A5.A.D.D3.A6.2AD.15D$66.D3.A.A3.D14.D2.A.A4.A.D.D
2.A5.2A2.D$66.D4.2A2.AD14.D.A4.A.A2.D.D.A4.2A4.D$66.D3.A2.2A.D14.D2.A
2.A2.A2.D.DA3.2A6.D$66.D2.A3.A.AD14.D4.A.2A3.D.D3.A.A.A.A2.D$66.D2.A
2.A.A.D14.D3.A.A.A3.D.D3.2A.A.A3.D$66.11D14.D5.2A2.2AD.D2.A2.2A4.AD$
66.D.A7.D14.D3.2A3.A.AD.D2.A.A2.A2.A.D$66.DA8.D14.D.2A4.A2.AD.D.A3.A
2.A.A.D$66.D3.A.A3.D14.D7.4AD.D.A2.A4.A.AD$66.D2.A4.A.D14.13D.DA6.2A
2.AD$66.D4.A.A2.D14.D.A.A.A5.D.DA5.A2.2A.D$66.D2.A2.2A2.D14.D2A4.A4.D
.14D$66.D4.2A2.AD14.D2.A2.A.A3.D$66.D3.A3.2AD14.DA3.A2.A3.D$66.D6.3AD
14.D3.2A3.A2.D$66.11D14.DA.A6.A.D$66.D.A7.D14.D.A6.2A.D$66.DA8.D14.D
2.2A6.AD$66.D4.A3.AD14.D4.A.A3.AD$66.D3.A3.A.D14.D5.2A2.2AD$66.D2.A3.
A2.D14.D7.4AD$66.D5.2A.AD14.13D$66.D4.2A.A.D14.D.A6.3AD$66.D3.A2.A.AD
14.DA4.3A3.D16.D.D.3D$66.D2.A2.A.A.D14.D4.A2.A2.AD16.D.D3.D$66.11D14.
D3.A2.A2.A.D16.3D.3D$66.D.A7.D14.D2.A2.A2.A2.D18.D3.D$66.DA8.D14.D.A
2.2A5.D18.D.3D$66.D4.A3.AD14.D.A.A3.A3.D$66.D3.A3.A.D14.D.2A3.A4.D16.
15D$66.D2.A3.A2.D14.DA3.A4.A.D16.DA12.D$66.D6.3AD14.DA2.A4.A2.D16.D.A
.A6.A.AD$66.D4.2A.A.D14.DA.A7.AD16.D.A2.A3.A2.A.D$66.D3.A.2A2.D14.13D
16.D.A3.A.A.A3.D$66.D2.A2.A2.AD43.D2.2A5.A.A.D$66.11D43.D2.A.A2.A4.AD
$66.DA8.D43.D2.A2.A2.A.A2.D$66.D5.A2.AD43.D3.A2.3A4.D$66.D4.A2.A.D43.
D4.A.A2.2A2.D$66.D3.A3.A.D43.D5.2A4.2AD$66.D2.A3.A2.D43.D7.6AD$66.D.A
4.A2.D43.15D$66.D4.3A2.D43.DA12.D$66.D2.2A4.AD43.D.2A7.A.AD$66.D.A5.
2AD43.D.A2.A3.A2.A.D$66.11D43.D.A3.A.A.A3.D$66.DA8.D43.D2.2A5.A.A.D$
66.D3.A2.A2.D43.D2.A3.3A4.D$66.D2.A3.A2.D43.D3.2A2.A4.AD$66.D.A5.A.D
43.D3.A.A2.A.A2.D$66.D4.A2.A.D43.D4.A.A2.2A2.D$66.D5.A2.AD43.D5.2A4.
2AD$66.D.2A5.AD43.D7.6AD$66.D3.2A3.AD43.15D$66.D5.3A.D43.DA12.D$66.
11D43.D.2A7.A.AD$66.DA8.D43.D.A.A5.A.A.D$66.D.2A6.D43.D.A4.3A4.D$66.D
.A4.A2.D43.D2.A.A3.A2.A.D$66.D4.A2.A.D43.D2.A2.A.A.A3.D$66.D3.A4.AD
43.D3.2A2.A4.AD$66.D5.A2.AD43.D3.A.A2.A.A2.D$66.D2.A4.2AD43.D4.A.A2.
2A2.D$66.D3.A2.2A.D43.D5.2A4.2AD$66.D4.3A2.D43.D7.6AD$66.11D43.15D$
66.DA8.D$66.D.A2.A4.D$66.D2.2A5.D$66.D2.A5.AD$66.D.A5.A.D$66.D5.2A2.D
$66.D5.A.2AD$66.D4.A.A.AD$66.D3.A2.2A.D$66.11D!

[dvgrn]

All non-isomorphic solutions to certain small square instances of the 3×3 and 4×4 Zarankiewicz's problem, as verified through SAT solving...

Is this a decent summary of Zarankiewicz's problem? It's a pretty sure sign that even the problem statement is over my head, when I can't even figure out what the definitions of "a" and "b" are.

[Freywa]

Is this a decent summary of Zarankiewicz's problem? It's a pretty sure sign that even the problem statement is over my head, when I can't even figure out what the definitions of "a" and "b" are.

Some of the results here (n >= 11 for 3×3, n >= 8 for 4×4) are genuinely new and proven by me. Indeed I've got an OEIS sequence with all the old and new data up in the 3×3 case.

[FractalFusion]

Is this a decent summary of Zarankiewicz's problem? It's a pretty sure sign that even the problem statement is over my head, when I can't even figure out what the definitions of "a" and "b" are.

The Zarankiewicz problem actually has multiple manifestations, but the basic idea given on Wikipedia as well as the site you linked is:

Given positive integers m,n and positive integers a,b where a≤m and b≤n, what is the maximum number k such that there exists a {0,1}-matrix of size m×n with k 1s which does not contain the all-1s matrix of size a×b as a submatrix?

(However, there are related definitions, such as on OEIS, where it appears the definition used for most of them is the minimum number k such that every {0,1}-matrix of size m×n with k 1s contains somewhere the all-1s matrix of size a×b as a submatrix. This is just the number in the previous definition plus 1.)

It took me some time to figure out, but it looks like Freywa is using a third definition: the minimum number k such that there exists a {0,1}-matrix of size m×n with k 1s which does not contain the all-0s matrix of size a×b as a submatrix. In the case of this post, only the cases a=b=3, m=n≥3 and a=b=4, m=n≥4 are considered. This is n² minus the number in the first definition, plus 1. Also, not only is k given, but also all possible matrices that achieve such k.

[Freywa]

Now with the 2×2 case:

Code: Select all

x = 310, y = 228, rule = LifeHistory
21.D4.3D3.3D4.D.3D3.3D.3D2.3D.3D3.D.D.3D4.3D.3D5.3D.3D6.3D.3D7.3D.3D
8.D.D.3D9.D.D.D.3D8.D.3D.D.D9.D.3D.3D10.3D.D.3D11.3D.D.D.3D10.3D.3D.
3D11.3D.3D.D.D12.3D.3D.3D$21.D6.D5.D4.D3.D5.D.D.D4.D.D.D3.D.D.D.D4.D
5.D5.D3.D8.D.D3.D7.D.D.D.D8.D.D3.D9.D.D.D.D.D8.D.D3.D.D9.D.D.D.D.D12.
D.D.D15.D.D.D3.D12.D3.D3.D13.D.D.D.D.D14.D3.D.D$21.D4.3D5.D4.D.3D3.3D
.D.D2.3D.3D3.3D.D.D4.3D.3D5.3D.3D6.3D.3D7.3D.3D8.D.D3.D9.D.3D.D.D8.D.
3D.3D9.D.3D.3D10.3D.D.3D11.3D.3D.3D10.3D3.D.3D11.3D.D.D.3D12.3D.3D.3D
$21.D6.D5.D4.D3.D3.D3.D.D2.D3.D.D5.D.D.D6.D.D7.D.D.D.D6.D.D.D11.D3.D
8.D.D3.D9.D3.D.D.D8.D.D.D3.D9.D.D.D3.D10.D3.D3.D11.D5.D3.D10.D5.D3.D
13.D.D.D3.D14.D3.D.D.D$21.D4.3D5.D4.D.3D3.3D.3D2.3D.3D5.D.3D4.3D.3D5.
3D.3D6.3D.3D7.3D.3D8.D.D3.D9.D3.D.3D8.D.3D3.D9.D.3D.3D10.3D.D.3D11.3D
3.D.3D10.3D3.D.3D11.3D.3D3.D12.3D.3D.3D2$3D5.3D10.4D.5D.6D.7D.8D.9D.
10D.11D.12D.13D.14D.15D.16D.17D.18D.19D.20D.21D.22D.23D$2.D.D.D3.D10.
DE.D.DA2.D.D2A2.D.D.2A2.D.D3A.A.D.D3A.A2.D.D6A2.D.D4A4.AD.D4.6AD.D2.
4A2.3AD.D5A2.2A.A.D.D5A2.2A.A.AD.D4.10AD.D2A4.8A.D.D3A5.8AD.D.5A4.7AD
.D2.7A3.6AD.D3.9A2.5AD.D4.12A.3AD.D2.4A.A.9A.2AD$3D2.D2.3D10.D2.D.D.A
.D.DA.A.D.DA2.A.D.D2A.A2.D.D2A.A2.AD.DA.A2.3AD.DA.5A2.D.D.3A2.4AD.D.A
.5A2.AD.D4A2.2A.A.AD.D4A2.2A.A.2AD.D.3A3.7AD.D6A4.4A.D.D3A.4A4.4AD.DA
.4A.3A3.4AD.D.A.9A3.3AD.D.2A2.9A2.3AD.D.3A3.10A.2AD.DA2.4A.A.9A.AD$D
3.D.D.D12.4D.D2.AD.D.2A.D.DA.A.AD.DA.A2.AD.DA.A2.2AD.D2A2.A.2AD.D3A.
2A.A.D.D.5A2.2AD.DA.A.4A.A.D.D3A2.2A.A.2AD.D3A2.2A.A.3AD.D.6A3.4AD.D.
A.3A.3A.4AD.D4A.3A.3A3.AD.D2A.4A.2A.2A2.2AD.DA2.12A3.D.D.4A2.9A2.AD.D
.6A3.8A.AD.D2A2.4A.A.9A.D$3D5.3D15.5D.D3.AD.D.A.2AD.D.A2.2AD.D.A2.3AD
.DA2.3A.AD.D2A.2A.2A.D.D.7A2.D.D2A.A.A.3A.D.D2A2.2A.A.3AD.D2A2.2A.A.
4AD.D.9A3.AD.D.2A.3A.3A.3AD.D2.3A.2A.7AD.D3A.4A.2A.A.A.AD.D3A2.4A.2A.
2A.2AD.DA.3A.A.6A.3A.D.D.9A3.6A.D.D.2A2.4A.A.9AD$32.6D.D2.3AD.DA2.3AD
.DA2.3A.D.DA.3A.A.D.D.3A.3A.D.DA.2A.A.A.AD.D3A.A2.2A.AD.DA2.2A.A.4AD.
DA2.2A.A.5AD.DA.2A.2A.2A.3AD.D.3A.3A.3A.2AD.D.A.A.4A.6AD.D4A.4A2.4A2.
D.D3A.A.4A.2A.2A.AD.DA.6A2.5A2.2AD.DA.2A.5A.2A.4A.AD.DA.2A2.4A.A.8AD$
39.7D.D2.3A.D.D2.3A.AD.D2A.A.2A.D.D.2A.A.3AD.DA.5A.A.D.D4A2.A2.2AD.D
2.2A.A.5AD.D2.2A.A.6AD.DA.3A.2A.2A.2AD.D.4A.3A.3A.AD.D.2A.8A.2A.D.D5A
.2A.3A.A.A.D.D4A2.5A.2A.2A.D.D2A2.6A.5A.A.D.DA.3A.A.6A.4A.D.D2A.2A2.
4A.A.7AD$39.D3A2.D.8D.D.3A.A.D.D.2A.3A.D.D.A.4A.AD.D2A.A.2A.2AD.D.2A
2.6AD.D.2A.A.6AD.D.2A.A.6A.D.DA.7A.2A2.D.DA2.6A.A.3AD.D.5A.3A.2A.2AD.
D2.11A.2A.D.D6A2.A.3A.3A.D.D2A.5A.2A.2A.2A.AD.DA.6A.2A.3A.A.2AD.D3A.
2A2.4A.A.6AD$39.D2A.A.D10.9D.D.3A3.AD.D2.4A.2AD.D2A.2A2.2A.D.D.4A.4A.
D.D2A.A.6A.D.D2A.A.6A2.D.D2A.A.3A.3A.AD.DA.A.4A.4A.AD.D.6A.3A.2A.AD.D
.A.9A.2A.AD.D6A.A.2A2.3A.AD.D3A.3A.A.2A.4A.AD.D2A.A.4A.5A.3A.D.D4A.2A
2.4A.A.5AD$39.DA.2A.D20.10D.DA4.4AD.D3A2.4A.D.DA2.2A.5AD.DA.A.6A2.D.D
A.A.6A2.AD.D2A.2A.A.5A.D.DA.2A.2A.2A.4AD.DA3.10A.AD.D.2A.A.4A.6AD.D7A
2.A.3A2.2AD.D4A.A.A.3A.5A.D.D2A.3A.4A.2A.3A.AD.D5A.2A2.4A.A.4AD$39.D.
3A.D20.D.6A.D.11D.D3A.A.A2.AD.DA.2A.4A.AD.D.A.6A2.AD.D.A.6A2.2AD.D2A.
3A.2A.A.2AD.DA.3A2.5A.2AD.DA.2A.5A.4A.D.D.3A.6A.2A.2AD.D.2A.4A.8A.D.D
4A.2A.3A.A.2A.2AD.D2A.4A.4A2.3A.2AD.D6A.2A2.4A.A.3AD$39.D4.AD20.D2A2.
A.2AD13.12D.D2A2.3A.3AD.DA.6A2.2AD.DA.6A2.2A.D.D3A2.6A.A.D.D2A.4A.4A
2.AD.DA.4A.4A2.3AD.DA2.A.3A.8AD.D.3A.2A.8A.AD.D5A.4A3.2A.3AD.D3A.A.6A
.2A.2A.AD.D7A.2A2.4A.A.2AD$39.7D20.DA2.A.3AD26.13D.D.6A2.2A.D.D.6A2.
2A.AD.D3A.A.3A2.3AD.D3A.5A2.A.2AD.DA.5A.A.3A.2AD.DA.A.5A.4A.2AD.D.4A
2.8A.2AD.D6A.2A2.2A2.4AD.D3A.2A.A.4A.5A.D.D8A.2A2.4A.A.AD$66.DA.A.2A.
AD40.14D.D6A2.2A.A.D.D3A.2A2.4A.AD.D4A.A.4A.A.AD.D2A.2A.5A.A.2AD.DA.
3A.A.7A.AD.DA.A.2A.7A.3AD.D.6A2.A.8AD.D3A.5A2.3A.2A.2AD.D9A.2A2.4A.A.
D$66.D2A.3A2.D55.15D.D6A.A.A.2A.D.D5A.2A.A2.3AD.D2A.3A.A.6A.D.D2A2.2A
.9A.D.DA.2A.3A.4A.4AD.D.8A.A.6A.D.D4A.3A.3A.A.A.3AD.D.9A.2A2.4A.AD$
66.DA.3A.A.D71.16D.D2.12A.D.D2A.4A.2A.A.3AD.D2A.2A.3A.A.5AD.DA.3A.A.
4A.5AD.DA.A.2A.4A.7AD.D5A.3A.A.A.2A.3AD.DA.9A.2A2.4A.D$66.D3A2.2A.D
88.17D.D5A.3A.4A2.D.D3A2.2A.4A.4AD.D2A2.3A.3A.6AD.DA.2A.5A.6A.AD.D6A
2.2A.4A2.3AD.D.A.9A.2A2.4AD$66.D.3A3.AD106.18D.D4A3.6A.3AD.D2A.A.A.3A
.7AD.D2A.A2.3A.9AD.D.12A3.4AD.DA.A.9A.2A2.3AD$66.10D106.D3A5.8AD.19D.
D2A.2A.2A2.8AD.D2A.3A2.7A.3AD.DA.4A.2A.2A.7AD.D2A.A.9A.2A2.2AD$66.D4A
.A2.D106.D3A.4A4.4AD21.20D.D3A.A.2A.4A.5AD.D2A.2A.2A.A.9AD.D3A.A.9A.
2A2.AD$66.D3A.A2.AD106.D3A.8A4.D42.21D.D3A2.2A.3A.8AD.D4A.A.9A.2A2.D$
66.D2A.A2.2AD106.D4.12AD64.22D.D.4A.A.9A.2A.D$66.DA.A2.3AD106.D.3A.3A
.3A.3AD87.23D$66.D.A2.4AD106.D.4A.3A.3A.2AD$66.DA2.4A.D106.D.5A.3A.3A
.AD$66.D2.4A.AD106.D.6A.3A.3A.D$66.D.4A.A.D106.DA.2A.6A.2A.AD$66.10D
106.DA.3A.4A.A.3AD$182.DA.4A.2A.5A.D$182.DA.5A2.4A.2AD$182.D2A.A.5A.
2A.2AD$182.D2A.2A.2A.6A.D$182.D2A.3A.4A2.3AD$182.D2A.4A.A.4A.AD$182.
18D$182.D3A5.8AD$182.D3A.4A4.4AD$182.D3A.8A4.D$21.D5.3D4.3D5.D.3D4.D.
3D5.3D.3D4.3D.3D5.D.D.3D6.3D.3D7.3D.D.D8.3D.3D9.3D.D12.D.3D.3D14.D4.
12AD$21.D7.D4.D7.D.D.D4.D.D9.D3.D6.D3.D5.D.D.D.D6.D5.D7.D3.D.D10.D3.D
9.D.D.D12.D.D.D.D16.D.3A.3A.3A.3AD$21.D5.3D4.3D5.D.D.D4.D.3D5.3D.3D4.
3D.3D5.3D.D.D6.3D.3D7.3D.3D10.D3.D9.3D.D12.D.D.D.3D14.D.4A.3A.3A.2AD$
21.D7.D6.D5.D.D.D4.D.D.D5.D3.D8.D.D9.D.D.D8.D.D9.D.D3.D10.D3.D11.D.D
12.D.D.D3.D14.D.5A.3A.3A.AD$21.D5.3D4.3D5.D.3D4.D.3D5.3D.3D4.3D.3D7.D
.3D6.3D.3D7.3D3.D10.D3.D9.3D.D12.D.3D.3D14.D.6A.3A.3A.D$182.DA.2A.6A.
2A.AD$3D5.3D10.5D.6D.7D.8D.9D.10D.11D.12D.13D.14D.15D.16D.17D6.DA.3A.
4A.4A.D$2.D.D.D3.D10.DA2.D.DA3.D.DA4.D.DA5.D.D2.2A3.D.D2.A.2A2.D.D.2A
6.D.D2A2.2A4.D.D2.2A4.2A.D.DA4.2A4.AD.D2.A4.4A2.D.D4.3A4.3AD.D8.7AD6.
DA.4A.2A.2A.3AD$3D2.D2.3D10.D3.D.D.A2.D.D.A3.D.D.2A3.D.D.A2.A2.D.D3.A
.2A.D.DA2.2A4.D.D3A3.A3.D.D.A4.2A.A.D.D3.2A.A2.2A.D.D2.5A6.D.D2.2A2.A
2.2A2.AD.D4.4A4.3AD6.DA.5A2.4A.2AD$2.D.D.D3.D10.D3.D.D2.A.D.D2.A2.D.D
.A.A2.D.DA4.A.D.DA3.A.A.D.DA4.2A2.D.D.3A3.A2.D.DA2.A.A.A3.D.D3.3A.2A
3.D.D3A8.2AD.D.A.A.A2.A.A.A.D.D2.2A2.2A2.2A2.AD6.D2A.A.5A.2A.2AD$3D5.
3D10.5D.D4.D.D3.A.D.D2.A.A.D.DA2.2A2.D.D2A3.A2.D.D.A2.A.2A.D.D2.3A3.A
.D.DA.A.A.A4.D.D.2A3.3A3.D.D.A3.2A2.2A.AD.D.2A.A3.2A.A2.D.D2.4A2.2A4.
AD6.D2A.2A.5A2.3AD$27.6D.D4.AD.D3.2A.D.D.A.A.A.D.D.2A3.A.D.D.A.A.A.A.
D.DA2.2A4.AD.D3.A.2A.A.AD.D.2A2.A3.2A.D.D.A2.A.A.A.2A.D.DA2.2A2.A2.2A
2.D.D.A.A.A.A.A.A.A.D6.D2A.3A.A.6A.D$34.7D.D5.AD.D2.A.2A.D.DA.2A4.D.D
2.A.2A2.AD.DA4.A.2A.D.D2.A.A2.2A.AD.DA.A.A3.A.A.D.D.A.A.A.A.A.A.D.DA.
A2.A.A.A2.A.D.D.A.2A.A.A.A2.A.D6.D2A.4A.A.4A.AD$42.8D.D6.AD.D.A.2A3.D
.D2.2A2.A.AD.D.A4.A.2AD.D.A.2A.A3.AD.D2A.A3.A.A2.D.D.A.2A2.2A3.AD.D2A
4.3A4.AD.D.2A2.2A.A2.2A2.D6.18D$51.9D.D7.AD.D3.2A2.2AD.D2.A2.A.A.AD.D
.2A2.A.A2.AD.D2.2A2.2A2.2AD.DA4.4A2.A.D.D4.7A3.D.D.2A.A2.A.2A.A2.D6.D
.3A3.8A.D$61.10D.D5.4AD.D3.A.2A.A.D.DA3.2A3.2AD.D2.2A.A2.2A.AD.DA3.A.
2A.A2.AD.D2.2A2.3A2.2A.D.DA2.A.2A2.2A.A2.D6.DA.5A3.5A.D$72.11D.D4.A.
2A.AD.D2A6.3AD.D.A2.A.A.2A.AD.DA2.A.A2.A.A.AD.D.A.A.A.A.A.A.AD.DA2.2A
2.2A2.2A2.D6.D4A.2A.2A3.3AD$72.D2A7.D.12D.D4.6A.D.D.A2.2A.A2.2AD.DA2.
2A4.3A.D.D.2A.A2.A2.A.2AD.DA.A2.A.2A.A2.A.D6.D5A.2A.A.2A2.AD$72.DA4.
4AD14.13D.DA6.5AD.D2.A.2A.A2.3AD.DA2.2A3.2A2.2AD.DA.A.A.A2.A.A.A.D6.D
.A.4A.5A.2AD$72.D4.3A2.D28.14D.D2.2A2.A.2A.2AD.DA.A2.A2.A.2A.AD.D2A4.
4A4.AD6.D.2A.4A.2A.4AD$72.D3.A.A.A.D28.D.4A3.A3.D.15D.D2A4.A2.4A.D.D
2A2.2A4.2A2.AD6.D.8A.2A.A.AD$72.D2.A2.A2.AD28.DA.2A.A3.A2.D17.16D.D4A
8.3AD6.DA2.A.9A.AD$72.D.4A4.D28.D2A.A2.A3.A.D34.17D6.DA.A.A.6A.3AD$
72.D.2A3.2A.D28.D3A4.A3.AD57.DA.4A.4A.A.2AD$72.D.A.A2.A.AD28.DA3.5A3.
D57.D2A2.6A.4A.D$72.D.A2.A2.2AD28.D.A2.4A.A2.D57.D2A.2A.3A.A.4AD$72.
11D28.D2.A.4A2.A.D57.D2A.3A.A.3A.3AD$72.DA7.AD28.D3.5A3.AD57.D3A2.4A.
3A.2AD$72.D.A2.A2.A.D28.DA3.A4.3AD57.D3A.2A2.6A.AD$72.D2.A.A.A2.D28.D
.A3.A2.A.2AD57.D2.8A.5AD$72.D3.3A3.D28.D2.A3.A.2A.AD57.18D$72.D4A5.D
28.D3.A3.4A.D$72.D3.A2.3AD28.14D$72.D2.A2.A.2AD$72.D.A3.2A.AD$72.DA3.
4A.D$72.11D$72.D2.2A4.AD$72.D.A.A3.A.D$72.DA.A3.A2.D$72.D2A3.A3.D$72.
D5.4AD$72.D3.4A2.D$72.D2.A.2A.A.D$72.D.A2.A.A.AD$72.DA3.A2.2AD$72.11D
$72.DA.A.A4.D$72.D.A3.2A2.D$72.DA5.2A.D$72.D3.A3.2AD$72.DA3.2A2.AD$
72.D.A2.A2.2AD$72.D.2A3.A.AD$72.D2.2A.A.A.D$72.D3.4A2.D$72.11D$72.DA
3.A3.AD$72.D.A2.A2.A.D$72.D2.A.A.A2.D$72.D3.3A3.D$72.D4A5.D$72.D3.A2.
3AD$72.D2.A2.A.2AD$72.D.A3.2A.AD$72.DA4.3A.D$72.11D$72.DA3.A3.AD$72.D
.A2.A2.A.D$72.D2.A.A.A2.D$72.D3.3A3.D$72.D4A5.D$72.D2.2A3.2AD$72.D.A.
A2.A.AD$72.DA.A2.A.A.D$72.D2A3.2A2.D$72.11D11$21.D6.3D5.3D6.3D7.D.3D
6.3D.3D5.3D.3D6.3D.3D7.D.D.D.D8.3D.3D$21.D8.D5.D10.D7.D3.D8.D.D.D7.D.
D10.D.D9.D.D.D.D8.D5.D$21.D6.3D5.3D8.D7.D.3D6.3D.D.D5.3D.3D6.3D.3D7.
3D.3D8.3D.3D$21.D8.D7.D8.D7.D3.D6.D3.D.D5.D3.D.D8.D3.D9.D3.D10.D.D$
21.D6.3D5.3D8.D7.D.3D6.3D.3D5.3D.3D6.3D.3D9.D3.D8.3D.3D2$D.D5.D.D10.
6D.7D.8D.9D.10D.11D.12D.13D.14D.15D$D.D.D.D.D.D10.DA3.D.DA4.D.DA5.D.D
A6.D.DA7.D.D.A7.D.D.A8.D.DA10.D.DA11.D.D5.2A2.A.A.D$3D2.D2.3D10.D4.D.
D.A3.D.D.A4.D.D.A5.D.D.A6.D.DA8.D.DA9.D.D.2A8.D.D3.A2.A2.A2.D.D4.2A2.
A.A2.D$2.D.D.D3.D10.D4.D.D2.A2.D.D2.A3.D.D2.A4.D.D2.A5.D.D7.2AD.D6.A.
2AD.D3.2A5.AD.D2.A.A3.A3.D.D3.2A2.A.A3.D$2.D7.D10.D4.D.D5.D.D3.A2.D.D
3.A3.D.D5.2A.D.D4.A.A2.D.D5.A.2A.D.D3.A.A3.A.D.D.A3.A.A4.D.D2.2A2.A.A
4.D$21.6D.D5.D.D4.A.D.D4.A2.D.D6.2AD.D3.A.A3.D.D4.A.2A2.D.D4.A.A.A2.D
.D2.A3.2A3.AD.D.2A2.A.A5.D$28.7D.D6.D.D5.A.D.D3.A3.AD.D4.2A2.AD.D3.A.
2A3.D.D5.3A3.D.D3.A.A2.A2.AD.D2A2.A.A6.D$36.8D.D6.AD.D3.2A3.D.D3.A2.
2A.D.D2.A.2A4.D.D.A4.A2.2AD.D.A2.A4.A.AD.DA2.A.A6.AD$45.9D.D4.2A2.D.D
2.A3.2A.D.D3.2A4.AD.D2.A2.A2.A.AD.D3.2A2.A2.A.D.D2.A.A6.2AD$55.10D.D
2.A2.A2.AD.D2.2A4.A.D.D2.A.A2.A.A.D.D2.A2.A3.2A.D.D.A.A6.2A.D$66.11D.
D2.A4.A.AD.D.A.A3.2A2.D.D.A4.A.A.A.D.DA.A6.2A2.D$66.D.A7.D.12D.D7.4AD
.D7.5AD.D.A6.2A2.AD$66.DA8.D14.13D.D4.3A3.2AD.DA6.2A2.A.D$66.D7.2AD
14.DA10.D.14D.D6.2A2.A.AD$66.D4.A.A2.D14.D.A.A5.A.D.D3.A6.2AD.15D$66.
D3.A.A3.D14.D2.A.A4.A.D.D2.A5.2A2.D$66.D4.2A2.AD14.D.A4.A.A2.D.D.A4.
2A4.D$66.D3.A2.2A.D14.D2.A2.A2.A2.D.DA3.2A6.D$66.D2.A3.A.AD14.D4.A.2A
3.D.D3.A.A.A.A2.D$66.D2.A2.A.A.D14.D3.A.A.A3.D.D3.2A.A.A3.D$66.11D14.
D5.2A2.2AD.D2.A2.2A4.AD$66.D.A7.D14.D3.2A3.A.AD.D2.A.A2.A2.A.D$66.DA
8.D14.D.2A4.A2.AD.D.A3.A2.A.A.D$66.D3.A.A3.D14.D7.4AD.D.A2.A4.A.AD$
66.D2.A4.A.D14.13D.DA6.2A2.AD$66.D4.A.A2.D14.D.A.A.A5.D.DA5.A2.2A.D$
66.D2.A2.2A2.D14.D2A4.A4.D.14D$66.D4.2A2.AD14.D2.A2.A.A3.D$66.D3.A3.
2AD14.DA3.A2.A3.D$66.D6.3AD14.D3.2A3.A2.D$66.11D14.DA.A6.A.D$66.D.A7.
D14.D.A6.2A.D$66.DA8.D14.D2.2A6.AD$66.D4.A3.AD14.D4.A.A3.AD$66.D3.A3.
A.D14.D5.2A2.2AD$66.D2.A3.A2.D14.D7.4AD$66.D5.2A.AD14.13D$66.D4.2A.A.
D14.D.A6.3AD$66.D3.A2.A.AD14.DA4.3A3.D16.D.D.3D$66.D2.A2.A.A.D14.D4.A
2.A2.AD16.D.D3.D$66.11D14.D3.A2.A2.A.D16.3D.3D$66.D.A7.D14.D2.A2.A2.A
2.D18.D3.D$66.DA8.D14.D.A2.2A5.D18.D.3D$66.D4.A3.AD14.D.A.A3.A3.D$66.
D3.A3.A.D14.D.2A3.A4.D16.15D$66.D2.A3.A2.D14.DA3.A4.A.D16.DA12.D$66.D
6.3AD14.DA2.A4.A2.D16.D.A.A6.A.AD$66.D4.2A.A.D14.DA.A7.AD16.D.A2.A3.A
2.A.D$66.D3.A.2A2.D14.13D16.D.A3.A.A.A3.D$66.D2.A2.A2.AD43.D2.2A5.A.A
.D$66.11D43.D2.A.A2.A4.AD$66.DA8.D43.D2.A2.A2.A.A2.D$66.D5.A2.AD43.D
3.A2.3A4.D$66.D4.A2.A.D43.D4.A.A2.2A2.D$66.D3.A3.A.D43.D5.2A4.2AD$66.
D2.A3.A2.D43.D7.6AD$66.D.A4.A2.D43.15D$66.D4.3A2.D43.DA12.D$66.D2.2A
4.AD43.D.2A7.A.AD$66.D.A5.2AD43.D.A2.A3.A2.A.D$66.11D43.D.A3.A.A.A3.D
$66.DA8.D43.D2.2A5.A.A.D$66.D3.A2.A2.D43.D2.A3.3A4.D$66.D2.A3.A2.D43.
D3.2A2.A4.AD$66.D.A5.A.D43.D3.A.A2.A.A2.D$66.D4.A2.A.D43.D4.A.A2.2A2.
D$66.D5.A2.AD43.D5.2A4.2AD$66.D.2A5.AD43.D7.6AD$66.D3.2A3.AD43.15D$
66.D5.3A.D43.DA12.D$66.11D43.D.2A7.A.AD$66.DA8.D43.D.A.A5.A.A.D$66.D.
2A6.D43.D.A4.3A4.D$66.D.A4.A2.D43.D2.A.A3.A2.A.D$66.D4.A2.A.D43.D2.A
2.A.A.A3.D$66.D3.A4.AD43.D3.2A2.A4.AD$66.D5.A2.AD43.D3.A.A2.A.A2.D$
66.D2.A4.2AD43.D4.A.A2.2A2.D$66.D3.A2.2A.D43.D5.2A4.2AD$66.D4.3A2.D
43.D7.6AD$66.11D43.15D$66.DA8.D$66.D.A2.A4.D$66.D2.2A5.D$66.D2.A5.AD$
66.D.A5.A.D$66.D5.2A2.D$66.D5.A.2AD$66.D4.A.A.AD$66.D3.A2.2A.D$66.11D
!

[Freywa]

The values given by Guy in his 1967 and 1969 papers for z(2,2, 14,n) for n >= 24 are WRONG.

Code: Select all

x = 30, y = 76, rule = LifeHistory
26D$D3A3.2A16.D$DA2.2A3.2A14.D$DA9.5A9.D$DA14.5A4.D$D.A.A.A4.A4.A8.D$
D.A2.A6.A4.A3.A3.D$D.A6.A3.A4.A3.2A.D$D2.2A9.A4.A2.A2.D$D2.A.2A8.A2.A
6.D$D2.A6.A.A3.A6.2AD$D3.A2.A7.A4.2A.A.D$D4.A2.A2.A8.A.A.AD$D5.2A.A4.
A2.A6.AD$D5.A.A.A2.A5.A.A3.D$27D$D3A3.2A17.D$DA2.2A3.2A15.D$DA9.5A10.
D$DA14.5A5.D$D.A.A6.A4.A4.A3.AD$D.A2.2A5.A4.A8.D$D.A6.A3.A4.A3.2A2.D$
D2.2A.A6.A5.A6.D$D2.A.A8.A3.A5.2AD$D2.A6.A.A7.3A3.D$D3.A2.A7.A.A4.A.A
.D$D4.A2.A6.A3.A.A.A2.D$D5.2A2.A3.A.A6.A2.D$D5.A.2A.A8.A3.A.D$28D$D4A
22.D$DA3.5A17.D$DA8.5A12.D$DA13.5A7.D$D.A2.A4.A4.A4.2A5.D$D.A3.A4.A4.
A5.2A3.D$D.A4.A4.A4.A6.2A.D$D2.A3.A2.A7.A3.A3.AD$D2.A4.A4.A3.A2.A2.A
3.D$D2.A5.A.A7.A.A2.A2.D$D3.A.A6.A4.A2.A3.A.D$D3.A3.A5.2A6.A.A2.D$D3.
A4.A2.A3.A3.A5.AD$D4.A8.A4.A3.A.2AD$29D$DA2.5A19.D$DA7.5A14.D$DA12.5A
9.D$DA17.5A4.D$D.A.A4.A4.A4.A4.A3.D$D.A2.A4.A4.A4.A4.A2.D$D.A3.A4.A4.
A4.A4.A.D$D.A4.A4.A4.A4.A4.AD$D2.2A7.A2.A7.A2.A.D$D2.A.A7.2A6.A5.AD$D
2.A2.A3.A7.A3.A.A3.D$D2.A4.A2.A5.A.A5.A2.D$D6.A5.A2.A6.3A2.D$D7.2A8.A
.A5.2AD$30D$DA2.5A20.D$DA7.5A15.D$DA12.5A10.D$DA17.5A5.D$D.A.A4.A4.A
4.A4.A4.D$D.A2.A4.A4.A4.A4.A3.D$D.A3.A4.A4.A4.A4.A2.D$D.A4.A4.A4.A4.A
4.A.D$D2.2A5.A7.A3.A3.A2.D$D2.A.A7.A3.A3.A2.A4.D$D2.A2.A2.A5.A7.A3.A.
D$D2.A4.A3.A3.A2.A5.A3.D$D6.A5.2A8.A.2A.AD$D7.A2.A6.A.A3.A2.2AD$30D!

[fluffykitty]

All non-isomorphic solutions to certain small square instances of the 3×3 and 4×4 Zarankiewicz's problem, as verified through SAT solving:

Code: Select all

hi

The 105 solution on the first row is constructible from the Fano plane. In this isomorphic form

Code: Select all

x = 15, y = 15, rule = b3s23
8b7o$4b7o$2b2o2b3o2b2o$2b4o2bo4b2o$bobobobobobobo$bob2obo2bo2bobo$b2o
2b2o3b2o2bo$b2obo2bo2bob2o$4o4b3o$2o2b2o2bo2b2o$2o4b3o4b2o$obobobo2bob
obo$obo2bobobo2bobo$o2b2o2bo2b2o2bo$o2bob2o3bob2o!

it can be describes as the block matrix [[0, 0s, 1s], [0s, 1s-(Fano plane incidence matrix), Fano], [1s, Fano, Fano]].

[Freywa]

The 105 solution on the first row is constructible from the Fano plane.

I already knew that – I have also proved that it is the unique extremal matrix (where graph isomorphism determines uniqueness) for z(3,3, 15,15).

The real challenge I'm facing now is to determine all non-isomorphic extremal matrices for z(2,2, 22,22) = 108. There are at least 10 of them.