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/