{
  "id": "1105.2419",
  "version": "v2",
  "published": "2011-05-12T10:47:38.000Z",
  "updated": "2012-09-22T11:23:05.000Z",
  "title": "Dense subsets of products of finite trees",
  "authors": [
    "Pandelis Dodos",
    "Vassilis Kanellopoulos",
    "Konstantinos Tyros"
  ],
  "comment": "36 pages, no figures; International Mathematics Research Notices, to appear",
  "journal": "International Mathematics Research Notices 4 (2013), 924-970",
  "doi": "10.1093/imrn/rns015",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove a \"uniform\" version of the finite density Halpern-L\\\"{a}uchli Theorem. Specifically, we say that a tree $T$ is homogeneous if it is uniquely rooted and there is an integer $b\\geq 2$, called the branching number of $T$, such that every $t\\in T$ has exactly $b$ immediate successors. We show the following. For every integer $d\\geq 1$, every $b_1,...,b_d\\in\\mathbb{N}$ with $b_i\\geq 2$ for all $i\\in\\{1,...,d\\}$, every integer $k\\meg 1$ and every real $0<\\epsilon\\leq 1$ there exists an integer $N$ with the following property. If $(T_1,...,T_d)$ are homogeneous trees such that the branching number of $T_i$ is $b_i$ for all $i\\in\\{1,...,d\\}$, $L$ is a finite subset of $\\mathbb{N}$ of cardinality at least $N$ and $D$ is a subset of the level product of $(T_1,...,T_d)$ satisfying \\[|D\\cap \\big(T_1(n)\\times ...\\times T_d(n)\\big)| \\geq \\epsilon |T_1(n)\\times ...\\times T_d(n)|\\] for every $n\\in L$, then there exist strong subtrees $(S_1,...,S_d)$ of $(T_1,...,T_d)$ of height $k$ and with common level set such that the level product of $(S_1,...,S_d)$ is contained in $D$. The least integer $N$ with this property will be denoted by $UDHL(b_1,...,b_d|k,\\epsilon)$. The main point is that the result is independent of the position of the finite set $L$. The proof is based on a density increment strategy and gives explicit upper bounds for the numbers $UDHL(b_1,...,b_d|k,\\epsilon)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-09-22T11:23:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "finite trees",
      "dense subsets",
      "level product",
      "explicit upper bounds",
      "branching number"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1105.2419D"
    }
  }
}