Source author record

Andrew Uzzell

Andrew Uzzell appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR

Catalog footprint

What is connected

4works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2018arXiv

On difference graphs and the local dimension of posets

The dimension of a partially-ordered set (poset), introduced by Dushnik and Miller (1941), has been studied extensively in the literature. Recently, Ueckerdt (2016) proposed a variation called local dimension which makes use of partial linear extensions. While local dimension is bounded above by dimension, they can be arbitrarily far apart as the dimension of the standard example is $n$ while its local dimension is only $3$. Hiraguchi (1955) proved that the maximum dimension of a poset of order $n$ is $n/2$. However, we find a very different result for local dimension, proving a bound of $Θ(n/\log n)$. This follows from connections with covering graphs using difference graphs which are bipartite graphs whose vertices in a single class have nested neighborhoods. We also prove that the local dimension of the $n$-dimensional Boolean lattice is $Ω(n/\log n)$ and make progress toward resolving a version of the removable pair conjecture for local dimension.

preprint2016arXiv

Monotone cellular automata in a random environment

In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in $\mathbb{Z}^d$ with random initial configurations. Formally, we are given a set $\mathcal{U}=\{X_1,\dots,X_m\}$ of finite subsets of $\mathbb{Z}^d\setminus\{\mathbf{0}\}$, and an initial set $A_0\subset\mathbb{Z}^d$ of `infected' sites, which we take to be random according to the product measure with density $p$. At time $t\in\mathbb{N}$, the set of infected sites $A_t$ is the union of $A_{t-1}$ and the set of all $x\in\mathbb{Z}^d$ such that $x+X\in A_{t-1}$ for some $X\in\mathcal{U}$. Our model may alternatively be thought of as bootstrap percolation on $\mathbb{Z}^d$ with arbitrary update rules, and for this reason we call it $\mathcal{U}$-bootstrap percolation. In two dimensions, we give a classification of $\mathcal{U}$-bootstrap percolation models into three classes -- supercritical, critical and subcritical -- and we prove results about the phase transitions of all models belonging to the first two of these classes. More precisely, we show that the critical probability for percolation on $(\mathbb{Z}/n\mathbb{Z})^2$ is $(\log n)^{-Θ(1)}$ for all models in the critical class, and that it is $n^{-Θ(1)}$ for all models in the supercritical class. The results in this paper are the first of any kind on bootstrap percolation considered in this level of generality, and in particular they are the first that make no assumptions of symmetry. It is the hope of the authors that this work will initiate a new, unified theory of bootstrap percolation on $\mathbb{Z}^d$.

preprint2016arXiv

Multicolour containers and the entropy of decorated graph limits

In recent breakthrough results, Saxton--Thomason and Balogh--Morris--Samotij have developed powerful theories of hypergraph containers. These theories have led to a large number of new results on transference, and on counting and characterising typical graphs in hereditary properties. In a different direction, Hatami--Janson--Szegedy proved results on the entropy of graph limits which count and characterise graphs in dense hereditary properties. In this paper, we make a threefold contribution to this area of research: 1) We generalise results of Saxton--Thomason to obtain container theorems for general, dense hereditary properties of multicoloured graphs. Our main tool is the adoption of an entropy-based framework. As corollaries, we obtain general counting, characterization and transference results. We further extend our results to cover a variety of combinatorial structures: directed graphs, oriented graphs, tournaments, multipartite graphs, multi-graphs, hypercubes and hypergraphs. 2) We generalise the results of Hatami--Janson--Szegedy on the entropy of graph limits to the setting of decorated graph limits. In particular we define a cut norm for decorated graph limits and prove compactness of the space of decorated graph limits under that norm. 3) We explore a weak equivalence between the container and graph limit approaches to counting and characterising graphs in hereditary properties. In one direction, we show how our multicolour container results may be used to recover decorated versions of the results of Hatami--Janson--Szegedy. In the other direction, we show that our decorated extensions of Hatami--Janson--Szegedy's results on graph limits imply counting and characterization applications. Similar container results were recently obtained independently by Terry.

preprint2012arXiv

A Turan-type problem on distances in graphs

We suggest a new type of problem about distances in graphs and make several conjectures. As a first step towards proving them, we show that for sufficiently large values of n and k, a graph on n vertices that has no three vertices at pairwise distance k has at most (n-k+1)^2/4 pairs of vertices at distance k.