Torsten Sillke, 10.12.92
17.03.93
01.05.98
Grid Avoidance Problems:
^^^^^^^^^^^^^^^^^^^^^^^^
no three in line:
=================
n*n grid:
maximal number of points: p(n)
bounds: (1.5 - epsilon) n <= p(n) <= 2n
examples with p(n) = 2n were found:
n (even) n <= 52
n (odd) n <= 45.
ref: Achim Flammenkamp, J. of Combinatorial Theory A 60 (1992) 305-311
Progress in the No-Three-in-Line-Problem
Achim Flammenkamp, J. of Combinatorial Theory A 81 (1998) 108-113
Progress in the No-Three-in-Line-Problem, II
mailto:achim@uni-bielefeld.de
http://www.uni-bielefeld.de/~achim/
n*n*n grid:
maximal number of points: p(n)
bounds: p(n) <= 2n*n
small values:
n p(n)
2 8
3 16
4 28 (Achim Flammenkamp)
5 38
6 64<=p(6)
n^d grid:
maximal number of points: p(n)
bounds: p(n) <= 2*n^(d-1)
3^n grid: ------- 10.03.93 --------
maximal number of points: p(n)
the lower bounds are from Chvatal.
(the first is the asymptotic of the second)
bounds: 3^(n+1) / Sqrt[Pi n] <= p(n) <= 2 3^(n-1)
A(n) = max { 2^(n-k) sum binomial(n,j) } <= p(n)
0<=k c + d.
Upper bounds:
2^(n/2 + O(sqrt(n))
this follows from pigenhole principle.
Lower bound:
BCH-codes of distance 5.
O( 2^(n/2) )
this code avoids projective planes.
bounds for small n:
n #A
2 3
3 5
4 7
5 12
6 16-18
7 23?-29
Optimal code for n=5
00000, 11111,
00011, 00110, 01100, 11000, 10001,
10101, 01011, 10110, 01101, 11010.
no parallel planes:
===================
n*n*n grid:
maximal number of points: p(n)
bounds: p(n) <= 2n+1
No parallel subspaces:
======================
Conjectures of Torsten Thiele:
Let P(n,d,q) be the maximal number of points of the n^d grid, such that
no two q-dimensional affine space (generated be q+1 points) are
parallel, (or the q+1 points are the same).
n^(d/3) <= P(n,d,1) <= n^(d^2/(2d+1))
no 1-dim affine subspace:
=========================
(Z3)^n ------- 08.06.93 --------
(see the analog question for the 3^n grid.)
small values: Brown, Buhler, Schroeppel
n p(n)
1 2
2 4
3 9
4 20
5 45<=p(5)
Richard Schroeppel wrote:
> I encountered the card game SET at a 1992 New Year's party, and pondered
> the puzzle of "what's the largest SETless group of cards?". In plainer
> language, "What's the largest subset of Z3^4 that contains no lines,
> even wraparound lines?".
>
>
> X-X --- -X-
> --- -X- X-X
> X-X --- -X-
>
> XX- X-X --- -X- --- --- ---
> X, XX-, XX-, --- -X- X-X, -X- --- -X-.
> --- X-X --- -X- --- --- ---
>
> -X- --- X-X
> X-X -X- ---
> -X- --- X-X
>
> I did a hand analysis proving that 20 is best possible in dimension 4,
> and darkened several mailboxes with it. It's 20KB; let me know if
> you want it. I mentioned the problem to Andy Odlyzko, who came up
> with some references; I haven't looked them up:
>
> > Regarding your puzzle, there is a paper of Brown and Buhler,
> JCT(A) 32 (1982), 20-34, which proves that the answer is
> o(3^n), but according to Buhler that is the best that is
> known. This paper mentions that for 5-dim., one can get
> 45 vectors, so the asyptotic answer is at least 45^(n/5),
> and since 45^(1/5) = 2.141..., that improves on the
> 20^(1/4) = 2.114... that you had.
>
> > Frankl, Graham, and Rodl, JCT(A) 45 (1987), 157-161 show that
> for large n one can get 2.179^n points.
>
> Rich rcs@cs.arizona.edu
never the same difference:
==========================
For all different 2-subsets {a, b}, {c, d} is a-b <> c-d.
So 3 <= #{ a, b, c, d } <= 4.
no parallelogram:
=================
For all different four points a, b, c, d is a-b <> c-d.
So #{ a, b, c, d } = 4.
n*n grid:
maximal number of points: p(n)
bounds: Omega(n^(2/3)/log(n)^(1/3)) <= p(n) <= Sqrt[8] n
small values:
n p(n)
2 3
3 5
4 7
n*n*n grid:
maximal number of points: p(n)
bounds: n <= p(n) <= O(n^1.5)
upper bouned see: parallel lines
no recktangles: ---------- 17.03.93 ----------
===============
n*n grid: Zarankiewicz problem
-3/2
lim z(n,n,2,2) n = 1
n->oo
Michael M"ors showed 1980:
-3/2 1/2
lim z(n,n,2,k) n = (k-1) for k >= 2.
n->oo
ref: M. M"ors, Das Problem von Zarankiewicz,
Dipom Thesis, univ. Bielefeld, 1980, p21 (10QA54.5M694)
no k-cycles
===========
2^n hypercube
ref: R. Entringer, K. A. Johnson,
Largest induced subgraphs of the n-cube that contain no 4-cycles
JoCT B
K. A. Johnson
A lower bound on largest induced subgraphs of the n-cube that
contain no 6-cycle
Congressus Numerantium 54 (1986) 181-190, Winnipeg
no 2^k cube
===========
2^n hypercube
ref: K. A. Johnson, Doctorial thesis,
Univ. of New Mexico, Summer 1986
some subgraphs
==============
2^n hypercube
ref: G. O. H. Katona, T. G. Tarjan
Extremal problems with excluded subgraphs in the n-cube,
Lecture Notes in Math. 1018, 84-93
Open problems in grid labeling
==============================
ref: Gallian, AMM 97 (1990) 133-135 #Zbl 741.05058
bandwidth( (P_3)^3 ) = 8 // better than left to rigth numbering
convex polygon
==============
how many points can a convex polygon have, which is imbedded
in a n*n grid? (T. Thiele, Diplom-Arbeit)
p(n)=c*n^(2/3)+O(n^(1/3)*log(n)), c=12/(2 pi)^(2/3).
convex polyhedron:
how many points can a convex polyhedron have, which is imbedded
in a n*n*n grid?
Imbeding a k*k grid into a n*n grid (T. Thiele)
===================================
how big must n be for a imbeding with the contraints:
1) the imbeding has no three in a line,
2) the orientation of three points of the k*k grid (not in a line)
is equal to the orientation of the imbeded points.
Let n(k) be the smallest n, such that the k*k grid can be
imbedded into the n*n grid with constraints (1) and (2).
The best bounds so far are:
1/4*k^2 <= n(k) = O(k^3).
The lower bound is a counting argument (no-three-in-line),
the upper bound comes from an explicit construction.
No squares (orthogonal):
========================
>Define q(n) as the maximal number of points that can be chosen from the n x n
>grid (or chess-board if you like), such that no four of the chosen points
>form the corners of an axis-parallel square.
n^(2-c/sqrt(log(n))) <= q(n).
this lower bound is from Torsten Thiele (probabilistic construction).
>What is the asymptotic behaviour of q(n) ? Is it quadratic, i.e. is there a
>constant c, such that
>
> q(n) >= c*n^2 ?
>>>> From: "Greg Kuperberg"
This would contradict the density Hales-Jewett theorem, which has been
claimed by Furstenburg. The theorem states that in an n-dimensional
cubical grid with k points on a side, the density of a collection of
points that contains no combinatorial line goes to zero as n goes to
infinity (with k fixed). Here a combinatorial line is a winning
progression in Tic-Tac-Toe, except that only diagonals with completely
positive slope are lines; antidiagonals are not considered.
Anyway, there is a map an n-dimensional cube with 4 points on a side
to a 2^n x 2^n grid that sends every combinatorial line to a square.
Namely, take the point (2a_0 + b_0,2a_1 + b_1, ... ,2a_n-1 + b_n-1)
to (a_0+2a_1+4a_2+...+2^n-1 a_n-1,b_0 + 2b_1 + ... + 2^n-1 b_n-1).
If all squares are disallowed in the target, all lines are disallowed
in the domain, and the density theorem applies.
Note: Furstenburg has a clean record of backing up announcements with
good proofs, but this particular result is rumored to be very hard and
I'm not completely sure that it has been checked to everyone's
satisfaction. Ron Graham has offered a monetary prize for it which may
not yet be in Furstenburg's pocket.
Question 1: Is this an example of killing a fly with a nuclear device?
Question 2: What happens if tilted squares are also disallowed?
Perhaps a complete solution is easier.
<<<<
No three-in-line and no four on a circle:
=========================================
Consider the following problem. (Torsten Thiele)
Let S(n,d) be the maximum number of points that can be chosen
from the n^d-grid (n x n x ... x n in d-space) with no d+2 points on
a sphere (S^(d-1)) and no d+1 points on a hyperplane. Assume d as a
constant.
The first observation is
S(n,d)=O(n).
It is well known that it is possible to choose Theta(n) points with
no d+1 on a hyperplane, skipping the sphere property. In two dimensions
I can show by a construction that
S(n,2)=Theta(n)
and similiar in higher dimensions
S(n,d)=Omega(n^(1/(d-1)).
But more should be possible. Does anybody know any result or reference
concerning this problem or a variation?
Torsten Thiele
mailto:thiele@math.fu-berlin.de
different distances
===================
3*3*3 grid 2-norm -> 5 points
1-norm -> 5 points
ref: Erdoes, Graham; Combinatorica 12 (1992) 39-44
Bounds for arrays of dots with distinct slopes or length
A better lower bound for points with distinct distances of the n*n grid
was found by Torsten Thiele (around 1992).
n^(2/3)
-------------
(log n)^(1/3).
other ramsey questions:
=======================
no monocromatic (aligned) squares:
colors = 2: maximal n*n grid found so far is n=13.
Robert Israel israel@math.ubc.ca
Department of Mathematics or israel@unixg.ubc.ca
University of British Columbia
Vancouver, BC, Canada V6T 1Y4
Chris Thompson
JANET: cet1@uk.ac.cam.phx
Internet: cet1@phx.cam.ac.uk
0001101010110
0101011000011
1100001101110
0110101011000
0101100001101
0000110101011
1011101100001
0110000110111
0011010101100
1010110000110
1000011011101
1101110110000
1011000011010
This 13*13 (0,1) square *does* satisfy the condition, having no
i x i and i x (13-i) rectangles with four corners the same.
As a matter of fact, there *is* something odd going on. A close look at
this solution shows that all the rows are cyclic permutations of
001101a101100, where "a" is either 0 or 1, each row being displaced 5
places to the left from the previous one. If you write one of these
13-tuples as _{i=0..12}, it satisfies the condition that for all
i and 1 <= j <= 12, c_i, c_{i+j}, c_{i+5j} and c_{i+6j} are not all the
same (considering the subscripts mod 13). Thus such a 13-tuple generates
a square that works (with periodic boundary condition). The only 13-tuples
for which this works are these two and those obtained from them by cyclic
permutation and interchanging 1 and 0. I also tried shifts other than 5
(so for some b, 1<=b<=12, you want c_i,c_{i+j},c_{i+bj} and c_{i+(b+1)j}
never to be all the same). No more examples except for b=8 (which is
equivalent to b=5 by left<->right symmetry). Unfortunately, there are no
14-, 15-, 16- or 17-tuples with the analogous properties either.
It really looks as thought there ought to be some significance in the fact
that 001101a101100 is the pattern of quadratic residues mod 13 (a at the
point 0 mod 13), and in the fact that 5 and 8 are the square roots of -1
mod 13. But naive attempts to use the same rules for larger primes don't
work. (They do work for N=5, 01a10 shifted 2 for each new row.)
no monocromatic square:
2 colors: maximal possible size is n=6
ref: Martin Gardner
New Mathematical Diversions from Scientific American
Simon & Schuster (1966)
MG3SA.12.1 The Game of Hip
MG3SA.12.1. two color the 6*6 square, s. t. there is no monochromatic square
MG3SA.12.1. the number of different squares in the n*n square is n^2(n^2-1)/12
no monocromatic (aligned) rectangle:
2 colors: Zarankiewicz problem
3 colors:
From: stein@hal.nta.no (Stein Kulseth)
Prove or disprove the statement:
A 12x12 point grid where the points are colored red, white and blue
contains a rectangle, aligned with the grid, such that all four corner
points are the same color.
NO:
chromatic rectangles: 2 colors: 3*7, 5*5,
3 colors: 4*19, 5*16, 7*13, 10*11.
IBM Nachrichten 39 (1989) Heft 298, 78
--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/