38
$\begingroup$

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} $ minor. The problem asks for the maximum possible number of entries equal to $1$. When $n=q^2+q+1$, one may take the incidence matrix of (points vs. lines in) the finite projective plane of order $q$, giving the answer $(q^2+q+1)(q+1)$. Moreover one can prove that this answer is optimal, when a projective plane of the right order exists. Since there is no finite projective plane of order $6$ one may ask

What is the maximum possible number of entries equal to $1$ in such a $43\times 43$ matrix?

The upper bound of $(6^2+6+1)(6+1)=301$ can not be achieved, but is the answer close to it?

The motivation here, is to understand if projective planes are "badly approximable" when they do not exist for a given order. One may speculate that the answer to the question above is given by cutting off from a projective plane of order $7$ a carefully chosen set of $13$ points and lines, but I'm not sure.

$\endgroup$
  • 2
    $\begingroup$ There is a lot of work on the Zarankiewicz problem but I don't recall any that specifically targets the sizes $t^2+t+1$ for $t$ not a prime power. Exact values are only known up to $n=31$ (myself and Narjess Afzaly, as yet unpublished). $\endgroup$ – Brendan McKay Dec 28 '14 at 0:42
  • 1
    $\begingroup$ It's infuriating that (as far as I can tell) there isn't an order-3 projective plane embedded as a subset of the order-7 projective plane, as excising it would give a tight lower bound of $300$. $\endgroup$ – Adam P. Goucher Jan 26 '15 at 0:14
  • $\begingroup$ compare oeis.org/A072567 $\endgroup$ – Moritz Firsching Mar 30 '15 at 9:54
  • $\begingroup$ A plane of order $7$ has $7^2+7+1=57$ points and lines, so deleting $13$ points/lines would leave a $44 \times 44$ matrix? Or am I missing something? $\endgroup$ – Gordon Royle Mar 30 '15 at 10:41
  • 1
    $\begingroup$ This question made me wonder if we can define such a thing as 'an approximation to a finite geometry'? Ideally something that could often be used as a good alternative for orders where perfect geometries don't exist? $\endgroup$ – Thomas Dybdahl Ahle Sep 27 '16 at 9:08
16
$\begingroup$

I tried this years ago (mid 1990's) and with much slower computers could never get over 290. Here's one example with 290.

0000000010000000010110000000000010011000000 0000001010010000000000000010000001000001001 1000000001000100000000001000010000000101000 0100000101000000000000010100000000010000001 0010000000000101100000000001000000010000000 1000100110000000101000000000000000100000000 1000011000000001000101010000000000000000000 1001000000000000000010000111000100000000000 0010100000000000000001000100000000001001000 0000000000100000000010010000100000100001000 1010000000001000010000000000101000000000001 0000000001100000100000100010001000001000000 1000000000010010000000100000000000010010000 0000000010100011000000001100000000000000010 0101010010000100000000100000100000000000000 0000000100010001000000000000100100001100000 0000000010000000000000010001001000000100100 0000100000000001000010100000010000000000101 0000000000000000100100000100110001000010000 0000000000100100001100000000000100000000001 0000001000000000000000000000011100110000010 0001000000000000100001000000000010000100011 0001000001000001010000000000000001100000000 0000000000000000001001001010100000010000100 0000010000000000000000001001000000101010001 0000100000000100010000010010000000000010010 0000000011001000000001000000000100000010000 0000101001000010000000000001100010000000000 0100000000000001001000000000001010000011000 0011001100100000000000000000000000000010100 0000000100000110000011000000001001000000000 0100001000001000100010001000000000000000000 0100000000110000010001000001010000000000000 0000000000011100000000000100000010100000100 0000000100001000000100100001000000000001010 0001000000001010001000010000010000001000000 0000110000101000000000000000000001010100000 0110000000000010000100000010000000100100000 0000010000000010110000000000000100000001100 0010000000000000000000111000000111000000000 1100000000000000000000000000000001001000110 0000001000000000011000100100000000000100000 0010010001010000001010000000000000000000010

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Me funksionin GAP

MaxOnes := n -> Maximum(List(Filtered(AsList(GF(2)^[n,n]),
                             M->not ForAny(Tuples([1..n-1],2),
                                           s->ForAny(Cartesian([1..n-s[1]],[1..n-s[2]]),
                                                     t->ForAll(Flat(M{[s[1],s[1]+t[1]]}
                                                                     {[s[2],s[2]+t[2]]}),
                                                               IsOne)))),
                             N->Number(Flat(N),IsOne)));

ne kemi per shembull

gap> MaxOnes(1);
1
gap> MaxOnes(2);
3
gap> MaxOnes(3);
6
gap> MaxOnes(4);
9

dhe pergjigja e pyetjes eshte

gap> MaxOnes(43);
( ... ju lutem prisni ... ju lutem prisni ... !! )
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Albanian${}{}$? $\endgroup$ – Gerry Myerson Mar 29 '15 at 10:58
  • 6
    $\begingroup$ Google translate tells me it's Albanian. I won't speculate on the reasons for writing in Albanian, but the name Gjergji Zaimi is certainly plausibly Albanian in origin. Of course it's pretty easy to figure out more or less what is being said, but "ne kemi per shembull" translates to "we have for example", and "dhe pergjigja e pyetjes eshte" to "and the answer to the question is", and "ju lutem prisni" to "please wait", and the gist of the rest is, I think, that the computer was taking too long; presumably more speed and memory would be required to obtain the answer. $\endgroup$ – Todd Trimble Mar 29 '15 at 12:05
  • 2
    $\begingroup$ Stefan Kohl worked in Albania for a number of years... $\endgroup$ – Dima Pasechnik Apr 5 '15 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.