BZPEER

preprint2022arXiv

Accumulation points of the edit distance function

Given a hereditary property $\mathcal H$ of graphs and some $p\in[0,1]$ , the edit distance function $\operatorname{ed}_{\mathcal H}(p)$ is (asymptotically) the maximum proportion of "edits" (edge-additions plus edge-deletions) necessary to transform any graph of density $p$ into a member of $\mathcal H$ . For any fixed $p\in[0,1]$ , $\operatorname{ed}_{\mathcal H}(p)$ can be computed from an object known as a colored regularity graph (CRG). This paper is concerned with those points $p\in[0,1]$ for which infinitely many CRGs are required to compute $\operatorname{ed}_{\mathcal H}$ on any open interval containing $p$ ; such a $p$ is called an accumulation point. We show that, as expected, $p=0$ and $p=1$ are indeed accumulation points for some hereditary properties; we additionally determine the slope of $\operatorname{ed}_{\mathcal H}$ at these two extreme points. Unexpectedly, we construct a hereditary property with an accumulation point at $p=1/4$ . Finally, we derive a significant structural property about those CRGs which occur at accumulation points.

preprint2022arXiv

Counting paths, cycles and blow-ups in planar graphs

For a planar graph $H$ , let $\operatorname{\mathbf{N}}_{\mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$ -vertex planar graph. In this paper, we prove that $\operatorname{\mathbf{N}}_{\mathcal P}(n,P_7)\sim{4\over 27}n^4$ , $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_6)\sim(n/3)^3$ , $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_8)\sim(n/4)^4$ and $\operatorname{\mathbf{N}}_{\mathcal P}(n,K_4\{1\})\sim(n/6)^6$ , where $K_4\{1\}$ is the $1$ -subdivision of $K_4$ . In addition, we obtain significantly improved upper bounds on $\operatorname{\mathbf{N}}_{\mathcal P}(n,P_{2m+1})$ and $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_{2m})$ for $m\geq 4$ . For a wide class of graphs $H$ , the key technique developed in this paper allows us to bound $\operatorname{\mathbf{N}}_{\mathcal P}(n,H)$ in terms of an optimization problem over weighted graphs.

preprint2022arXiv

Induced and non-induced poset saturation problems

A subfamily $\mathcal{G}\subseteq \mathcal{F}\subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal{F}$ if there exists a bijection $i:P\rightarrow \mathcal{G}$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$ . In the case where in addition $p\le_P q$ holds if and only if $i(p)\subseteq i(q)$ , then $\mathcal{G}$ is an induced (strong) copy of $P$ in $\mathcal{F}$ . We consider the minimum number $sat(n,P)$ [resp.\ $sat^*(n,P)$ ] of sets that a family $\mathcal{F}\subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G\in 2^{[n]}\setminus \mathcal{F}$ creates a non-induced [induced] copy of $P$ . We prove for any finite poset $P$ that $sat(n,P)\le 2^{|P|-2}$ , a bound independent of the size $n$ of the ground set. For induced copies of $P$ , there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$ . We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets. Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$ -freeness, we tend to get a small size non-induced [induced] $P$ -saturating family.

preprint2020arXiv

Counterexamples to a conjecture of Harris on Hall ratio

The Hall ratio of a graph $G$ is the maximum value of $v(H) / α(H)$ taken over all non-null subgraphs $H$ of $G$ . For any graph, the Hall ratio is a lower-bound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.

preprint2020arXiv

On the edit distance function of the random graph

Given a hereditary property of graphs $\mathcal{H}$ and a $p\in [0,1]$ , the edit distance function ${\rm ed}_{\mathcal{H}}(p)$ is asymptotically the maximum proportion of edge-additions plus edge-deletions applied to a graph of edge density $p$ sufficient to ensure that the resulting graph satisfies $\mathcal{H}$ . The edit distance function is directly related to other well-studied quantities such as the speed function for $\mathcal{H}$ and the $\mathcal{H}$ -chromatic number of a random graph. Let $\mathcal{H}$ be the property of forbidding an Erdős-Rényi random graph $F\sim \mathbb{G}(n_0,p_0)$ , and let $φ$ represent the golden ratio. In this paper, we show that if $p_0\in [1-1/φ,1/φ]$ , then a.a.s. as $n_0\to\infty$ , \begin{align*} {\rm ed}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $p\in [1/3,2/3]$ for any $p_0\in (0,1)$ .

preprint2020arXiv

Planar Turán number of the 6-cycle

Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$ -vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$ , ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well studied function, the planar Turán number of $H$ , denoted by ${\rm ex}_{\mathcal{P}}(n,H)$ . The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$ . Later on, Y. Lan, et al. continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$ . In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$ , for all $n\geq 18$ , which improves Lan's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$ , for $k\geq 7$ .

preprint2019arXiv

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~ $G$ begin in one of two states, "dormant" or "active". Given a fixed integer $r$ , a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$ , we say that $G$ $r$ -percolates (from $A$ ) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$ -percolates from $A$ . Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$ . In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $σ_2(G)\ge n-2$ , then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chvátal-type degree condition: If $G$ is a graph with degree sequence $d_1\le d_2\le\dots\le d_n$ such that $d_i \geq i+1$ or $d_{n-i} \geq n-i-1$ for all $1 \leq i < \frac{n}{2}$ , then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. Combin.]

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.

preprint2018arXiv

Polychromatic Colorings on the Integers

We show that for any set $S\subseteq \mathbb{Z}$ , $|S|=4$ there exists a 3-coloring of $\mathbb{Z}$ in which every translate of $S$ receives all three colors. This implies that $S$ has a codensity of at most $1/3$ , proving a conjecture of Newman [D. J. Newman, Complements of finite sets of integers, Michigan Math. J. 14 (1967) 481--486]. We also consider related questions in $\mathbb{Z}^d$ , $d\geq 2$ .

Ryan R. Martin

Research overview

Is this your work?

43 publications

Accumulation points of the edit distance function

Counting paths, cycles and blow-ups in planar graphs

Induced and non-induced poset saturation problems

Counterexamples to a conjecture of Harris on Hall ratio

On the edit distance function of the random graph

Planar Turán number of the 6-cycle

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

On difference graphs and the local dimension of posets

Polychromatic Colorings on the Integers

Q2Q_2Q2​-free families in the Boolean lattice

A note on GGG-intersecting families

A note on a conjecture of Gyárfás

A note on short cycles in a hypercube

A version of Szemerédi's regularity lemma for multicolored graphs and directed graphs that is suitable for induced graphs

Adding random edges to dense graphs

Avoiding patterns in matrices via a small number of changes

Edit distance and its computation

Expected values of parameters associated with the minimum rank of a graph

How many random edges make a dense graph hamiltonian?

Multicolor and directed edit distance

On Avoider-Enforcer games

On randomly generated intersecting hypergraphs

On randomly generated intersecting hypergraphs II

On the complexity of Chooser-Picker positional games

On the computation of edit distance functions

On the editing distance of graphs

On the path separation number of graphs

On the strong chromatic number of graphs

Rainbow arithmetic progressions

Regular colorings and factors of regular graphs

Sub-Ramsey numbers for arithmetic progressions

The diameter game

The edit distance function and symmetrization

The emergence of a giant component in random subgraphs of pseudo-random graphs

Tiling tripartite graphs with 3-colorable graphs

Tripartite Version of the Corrádi-Hajnal Theorem

An improved bound on the diamond-free poset problem

On the Edit Distance of Powers of Cycles

On the edit distance from K2,tK_{2,t}K2,t​-free graphs (Extended Version)

On the approximate shape of degree sequences that are not potentially HHH-graphic

Twins in graphs

Induced Saturation Number

On diamond-free subposets of the Boolean lattice

See the researcher in context

Building this map preview

$Q_2$ -free families in the Boolean lattice

A note on $G$ -intersecting families

On the edit distance from $K_{2,t}$ -free graphs (Extended Version)

On the approximate shape of degree sequences that are not potentially $H$ -graphic