39
$\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.

Improve this question
$\endgroup$
5
  • 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
    Commented Dec 28, 2014 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
    Commented Jan 26, 2015 at 0:14
  • $\begingroup$ compare oeis.org/A072567 $\endgroup$
    – Moritz Firsching
    Commented Mar 30, 2015 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
    Commented Mar 30, 2015 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
    Commented Sep 27, 2016 at 9:08

2 Answers 2

Reset to default
17
$\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

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 ... !! )
Improve this answer
$\endgroup$
3
  • $\begingroup$ Albanian${}{}$? $\endgroup$
    – Gerry Myerson
    Commented Mar 29, 2015 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
    Commented Mar 29, 2015 at 12:05
  • 2
    $\begingroup$ Stefan Kohl worked in Albania for a number of years... $\endgroup$
    – Dima Pasechnik
    Commented Apr 5, 2015 at 23:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .