The Analogue of Szemeredi's Theorem for Rectangles, n x n Lattice, Cuboid and n-Orthotope

Overview

Szemerédi's theorem asserts that all subset of the natural numbers with positive upper density contains arbitrary large infinitely many arithmetic progressions. This is the generalization of Van der Waerden’s theorem, a theorem in Ramsey theory. It states that if a sufficiently long interval of integers is partitioned into specific number of parts, one will contain an arithmetic progression of a given length. In this project we prove the analogue of Szemerédi’s theorem on the existence of a colored rectangle if some integer points in the plane are colored with positive density. Here the points are coloured monochromatically. We also prove the generalisations of the case of rectangle for nxn lattice (intersection points of n vertical and n horizontal lines) ,cuboid and n-orthotope (n-dimensional rectangle). We prove the result by creating an upper and lower bound on the maximum number of points coloured in a hypercube of side n such that no cuboid exists. We use principle of double counting, pigeonhole principle and Jensen's inequality to prove our result. For cuboids, the bounds obtained were of the order O(n^11/4) and o(n^5/2). The proof was extended for higher dimensions by using the bounds on n x n lattice and cuboid and the principle of mathematical induction. The result obtained has applications in graph theory. The maximum number of coloured points in a hypercube is equivalent to the maximum possible number of edges in an n-partite n-uniform hypergraph with no complete hypergraph with 2 vertices in each partite as a subgraph. This can be proved by showing a bijection between these two problems. Thus the analogue for rectangles and higher dimensions provides a generalization to Zarankiewicz problem , an unsolved problem of extremal graph theory.

Competition history

• ISEF 2018 Mathematics · Entry MATH050

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.