BZPEER

preprint2022arXiv

A Dual Ramsey theorem for trees

We prove a dualization of the Graham--Rothschild Theorem for variable words indexed by homogeneous trees.

preprint2021arXiv

A structure theorem for stochastic processes indexed by the discrete hypercube

Let $A$ be a finite set with $|A|\geqslant 2$ , let $n$ be a positive integer, and let $A^n$ denote the discrete $n$ -dimensional hypercube (that is, $A^n$ is the Cartesian product of $n$ many copies of $A$ ). Given a family $\langle D_t:t\in A^n\rangle$ of measurable events in a probability space (a stochastic process), what structural information can be obtained assuming that the events $\langle D_t:t\in A^n\rangle$ are not behaving as if they were independent? We obtain an answer to this problem (in a strong quantitative sense) subject to a mild "stationarity" condition. Our result has a number of combinatorial consequences, including a new (and the most informative so far) proof of the density Hales--Jewett theorem.

preprint2021arXiv

Subgaussianity is hereditarily determined

Let $n$ be a positive integer, let $\boldsymbol{X}=(X_1,\dots,X_n)$ be a random vector in $\mathbb{R}^n$ with bounded entries, and let $(θ_1,\dots,θ_n)$ be a vector in $\mathbb{R}^n$ . We show that the subgaussian behavior of the random variable $θ_1 X_1+\dots +θ_n X_n$ is essentially determined by the subgaussian behavior of the random variables $\sum_{i\in H} θ_i X_i$ where $H$ is a random subset of $\{1,\dots,n\}$ .

preprint2016arXiv

A concentration inequality for product spaces

We prove a concentration inequality which asserts that, under some mild regularity conditions, every random variable defined on the product of sufficiently many probability spaces exhibits pseudorandom behavior.

preprint2016arXiv

The Bradley--Terry condition is $L_1$ --testable

We provide an algorithm with constant running time that given a weighted tournament $T$ , distinguishes with high probability of success between the cases that $T$ can be represented by a Bradley--Terry model, or cannot even be approximated by one. The same algorithm tests whether the corresponding Markov chain is reversible.

preprint2015arXiv

A density version of the Carlson--Simpson theorem

We prove a density version of the Carlson--Simpson Theorem. Specifically we show the following. For every integer $k\geq 2$ and every set $A$ of words over $k$ satisfying $\limsup_{n\to\infty} \frac{|A\cap [k]^n|}{k^n}>0$ there exist a word $c$ over $k$ and a sequence $(w_n)$ of left variable words over $k$ such that the set $\{c\}\cup \big\{c^{\smallfrown}w_0(a_0)^{\smallfrown}...^{\smallfrown}w_n(a_n) : n\in\mathbb{N} \ \text{ and } \ a_0,...,a_n\in [k]\big\}$ is contained in $A$ . While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

preprint2015arXiv

Primitive recursive bounds for the finite version of Gowers' $c_0$ theorem

We provide primitive recursive bounds for the finite version of Gowers' $c_0$ theorem for both the positive and the general case. We also provide multidimensional versions of these results.

preprint2014arXiv

A disjoint union theorem for trees

We prove an infinitary disjoint union theorem for level products of trees. To implement the proof we develop a Hales-Jewett type result for words indexed by a level product of trees.

preprint2014arXiv

Measurable events indexed by words

For every integer $k\geq 2$ let $[k]^{<\mathbb{N}}$ be the set of all words over $k$ , that is, all finite sequences having values in $[k]:=\{1,...,k\}$ . A Carlson-Simpson tree of $[k]^{<\mathbb{N}}$ of dimension $m\geq 1$ is a subset of $[k]^{<\mathbb{N}}$ of the form $\{w\}\cup \big\{w^{\smallfrown}w_0(a_0)^{\smallfrown}...^{\smallfrown}w_{n}(a_n): n\in \{0,...,m-1\} \text{ and } a_0,...,a_n\in [k]\big\}$ where $w$ is a word over $k$ and $(w_n)_{n=0}^{m-1}$ is a finite sequence of left variable words over $k$ . We study the behavior of a family of measurable events in a probability space indexed by the elements of a Carlson-Simpson tree of sufficiently large dimension. Specifically we show the following. For every integer $k\geq 2$ , every $0<\varepsilon\leq 1$ and every integer $n\geq 1$ there exists a strictly positive constant $θ(k,\varepsilon,n)$ with the following property. If $m$ is a given positive integer, then there exists an integer $\mathrm{Cor}(k,\varepsilon,m)$ such that for every Carlson--Simpson tree $T$ of $[k]^{<\mathbb{N}}$ of dimension at least $\mathrm{Cor}(k,\varepsilon,m)$ and every family $\{A_t:t\in T\}$ of measurable events in a probability space $(Ω,Σ,μ)$ satisfying $μ(A_t)\geq \varepsilon$ for every $t\in T$ , there exists a Carlson--Simpson tree $S$ of dimension $m$ with $S\subseteq T$ and such that for every nonempty $F\subseteq S$ we have $μ\Big(\bigcap_{t\in F} A_t\Big) \geq θ(k,\varepsilon,|F|).$ The proof is based, among others, on the density version of the Carlson--Simpson Theorem established recently by the authors, as well as, on a partition result -- of independent interest -- closely related to the work of T. J. Carlson, and H. Furstenberg and Y. Katznelson. The argument is effective and yields explicit lower bounds for the constants $θ(k,\varepsilon,n)$ .

preprint2014arXiv

On colorings of variable words

In this note, we prove that the base case of the Graham--Rothschild Theorem, i.e., the one that considers colorings of the ( $1$ -dimensional) variable words, admits bounds in the class $\mathcal{E}^5$ of Grzegorczyk's hierarchy.

preprint2014arXiv

On the structure of the set of higher order spreading models

We generalize some results concerning the classical notion of a spreading model for the spreading models of order $ξ$ . Among them, we prove that the set $SM_ξ^w(X)$ of the $ξ$ -order spreading models of a Banach space $X$ generated by subordinated weakly null $\mathcal{F}$ -sequences endowed with the pre-partial order of domination is a semi-lattice. Moreover, if $SM_ξ^w(X)$ contains an increasing sequence of length $ω$ then it contains an increasing sequence of length $ω_1$ . Finally, if $SM_ξ^w(X)$ is uncountable, then it contains an antichain of size the continuum.

preprint2013arXiv

A simple proof of the density Hales-Jewett theorem

We give a purely combinatorial proof of the density Hales--Jewett Theorem that is modeled after Polymath's proof but is significantly simpler. In particular, we avoid the use of the equal-slices measure and work exclusively with the uniform measure.

preprint2013arXiv

Combinatorial Structures on van der Waerden sets

In this paper we provide two results. The first one consists an infinitary version of the Furstenberg-Weiss Theorem. More precisely we show that every subset $A$ of a homogeneous tree $T$ such that $\frac{|A\cap T(n)|}{|T(n)|}\geqδ$ , where T(n) denotes the $n$ -th level of $T$ , for all $n$ in a van der Waerden set, for some positive real $δ$ , contains a strong subtree having a level sets which forms a van der Waerden set. The second result is the following. For every sequence $(m_q)_{q}$ of positive integers and for every real $0<δ\\leq1$ , there exists a sequence $(n_q)_{q}$ of positive integers such that for every $D\subseteq \bigcup_k\prod_{q=0}^{k-1}[n_q]$ satisfying $$\frac{\big{|}D\cap \prod_{q=0}^{k-1} [n_q]\big{|}}{\prod_{q=0}^{k-1}n_q}\geqδ$$ for every $k$ in a van der Waerden set, there is a sequence $(J_q)_{q}$ , where $J_q$ is an arithmetic progression of length $m_q$ contained in $[n_q]$ for all $q$ , such that $\prod_{q=0}^{k-1}J_q\subseteq D$ for every $k$ in a van der Waerden set. Moreover, working in an abstract setting, we obtain $J_q$ to be any configuration of natural numbers that can be found in an arbitrary set of positive density.

preprint2013arXiv

Measurable events indexed by products of trees

A tree $T$ is said to be homogeneous if it is uniquely rooted and there exists an integer $b\meg 2$, called the branching number of $T$ , such that every $t\in T$ has exactly $b$ immediate successors. A vector homogeneous tree $\mathbf{T}$ is a finite sequence $(T_1,...,T_d)$ of homogeneous trees and its level product $\otimes\mathbf{T}$ is the subset of the cartesian product $T_1\times ...\times T_d$ consisting of all finite sequences $(t_1,...,t_d)$ of nodes having common length. We study the behavior of measurable events in probability spaces indexed by the level product $\otimes\mathbf{T}$ of a vector homogeneous tree $\mathbf{T}$ . We show that, by refining the index set to the level product $\otimes\mathbf{S}$ of a vector strong subtree $\bfcs$ of $\mathbf{S}$ , such families of events become highly correlated. An analogue of Lebesgue's density Theorem is also established which can be considered as the "probabilistic" version of the density Halpern--Läuchli Theorem.

preprint2012arXiv

Dense subsets of products of finite trees

We prove a "uniform" version of the finite density Halpern-Lä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<ε\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 ε|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,ε)$ . 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,ε)$ .

preprint2012arXiv

Measurable events indexed by trees

A tree $T$ is said to be homogeneous if it is uniquely rooted and there exists an integer $b\geq 2$ , called the branching number of $T$ , such that every $t\in T$ has exactly $b$ immediate successors. We study the behavior of measurable events in probability spaces indexed by homogeneous trees. Precisely, we show that for every integer $b\geq 2$ and every integer $n\geq 1$ there exists an integer $q(b,n)$ with the following property. If $T$ is a homogeneous tree with branching number $b$ and $\{A_t:t\in T\}$ is a family of measurable events in a probability space $(Ω,Σ,μ)$ satisfying $μ(A_t)\geqε>0$ for every $t\in T$ , then for every $0<θ<ε$ there exists a strong subtree $S$ of $T$ of infinite height such that for every non-empty finite subset $F$ of $S$ of cardinality $n$ we have \[ μ\Big(\bigcap_{t\in F} A_t\Big) \meg θ^{q(b,n)}. \] In fact, we can take $q(b,n)= \big((2^b-1)^{2n-1}-1\big)\cdot(2^b-2)^{-1}$ . A finite version of this result is also obtained.

preprint2012arXiv

Oscilation stability for continuous monotone surjections

We prove that for every integer $b\geqslant 2$ and positive real $\varepsilon$ there exists a finite number $t$ such that for every finite coloring of the nondecreasing surjections from $b^ω$ onto $b^ω$ , there exist $t$ many colors such that their $\varepsilon$ -fattening contains a cube.

preprint2012arXiv

Subsets of Products of Finite Sets of Positive Upper Density

In this note we prove that for every sequence $(m_q)_{q}$ of positive integers and for every real $0<δ\leqslant1$ there is a sequence $(n_q)_{q}$ of positive integers such that for every sequence $(H_q)_{q}$ of finite sets such that $|H_q|=n_q$ for every $q\in\mathbb{N}$ and for every $D\subseteq \bigcup_k\prod_{q=0}^{k-1}H_q$ with the property that $\limsup_k \frac{|D\cap \prod_{q=0}^{k-1} H_q|}{|\prod_{q=0}^{k-1}H_q|}\geqslantδ$ there is a sequence $(J_q)_{q}$ , where $J_q\subseteq H_q$ and $|J_q|=m_q$ for all $q$ , such that $\prod_{q=0}^{k-1}J_q\subseteq D$ for infinitely many $k.$ This gives us a density version of a well-known Ramsey-theoretic result. We also give some estimates on the sequence $(n_q)_{q}$ in terms of the sequence of $(m_q)_{q}$ .

Konstantinos Tyros

Research overview

Is this your work?

18 publications

A Dual Ramsey theorem for trees

A structure theorem for stochastic processes indexed by the discrete hypercube

Subgaussianity is hereditarily determined

A concentration inequality for product spaces

The Bradley--Terry condition is $L_1$ --testable

A density version of the Carlson--Simpson theorem

Primitive recursive bounds for the finite version of Gowers' $c_0$ theorem

A disjoint union theorem for trees

Measurable events indexed by words

On colorings of variable words

On the structure of the set of higher order spreading models

A simple proof of the density Hales-Jewett theorem

Combinatorial Structures on van der Waerden sets

Measurable events indexed by products of trees

Dense subsets of products of finite trees

Measurable events indexed by trees

Oscilation stability for continuous monotone surjections

Subsets of Products of Finite Sets of Positive Upper Density

See the researcher in context

Building this map preview

Konstantinos Tyros

Research overview

Is this your work?

18 publications

A Dual Ramsey theorem for trees

A structure theorem for stochastic processes indexed by the discrete hypercube

Subgaussianity is hereditarily determined

A concentration inequality for product spaces

The Bradley--Terry condition is L1L_1L1​--testable

A density version of the Carlson--Simpson theorem

Primitive recursive bounds for the finite version of Gowers' c0c_0c0​ theorem

A disjoint union theorem for trees

Measurable events indexed by words

On colorings of variable words

On the structure of the set of higher order spreading models

A simple proof of the density Hales-Jewett theorem

Combinatorial Structures on van der Waerden sets

Measurable events indexed by products of trees

Dense subsets of products of finite trees

Measurable events indexed by trees

Oscilation stability for continuous monotone surjections

Subsets of Products of Finite Sets of Positive Upper Density

See the researcher in context

Building this map preview

The Bradley--Terry condition is $L_1$ --testable

Primitive recursive bounds for the finite version of Gowers' $c_0$ theorem