Blog
About

9
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Density Hales-Jewett and Moser numbers

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          For any \(n \geq 0\) and \(k \geq 1\), the \emph{density Hales-Jewett number} \(c_{n,k}\) is defined as the size of the largest subset of the cube \([k]^n\) := \(\{1,...,k\}^n\) which contains no combinatorial line; similarly, the Moser number \(c'_{n,k}\) is the largest subset of the cube \([k]^n\) which contains no geometric line. A deep theorem of Furstenberg and Katznelson shows that \(c_{n,k}\) = \(o(k^n)\) as \(n \to \infty\) (which implies a similar claim for \(c'_{n,k}\)); this is already non-trivial for \(k = 3\). Several new proofs of this result have also been recently established. Using both human and computer-assisted arguments, we compute several values of \(c_{n,k}\) and \(c'_{n,k}\) for small \(n,k\). For instance the sequence \(c_{n,3}\) for \(n=0,...,6\) is \(1,2,6,18,52,150,450\), while the sequence \(c'_{n,3}\) for \(n=0,...,6\) is \(1,2,6,16,43,124,353\). We also prove some results for higher \(k\), showing for instance that an analogue of the LYM inequality (which relates to the \(k = 2\) case) does not hold for higher \(k\), and also establishing the asymptotic lower bound \(c_{n,k} \geq k^n \exp(- O(\sqrt[\ell]{\log n}))\) where \(\ell\) is the largest integer such that \(2k > 2^\ell\).

          Related collections

          Most cited references 3

          • Record: found
          • Abstract: not found
          • Article: not found

          Ein Satz �ber Untermengen einer endlichen Menge

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            A density version of the Hales-Jewett theorem

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Primitive recursive bounds for van der Waerden numbers

                Bookmark

                Author and article information

                Journal
                01 February 2010
                2010-04-25
                Article
                1002.0374

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                05D05, 05D10
                49 pages. To appear, Szemeredi birthday conference proceedings
                math.CO

                Comments

                Comment on this article