Ryan R. Martin

activity

20062023

most citedAdding random edges to dense graphs

53 citations · 365 across the 52 of their papers we have counts for

collaborators

64 papers

math.CO2023★ 2 cited

The maximum number of odd cycles in a planar graph

Emily Heath, Ryan R. Martin, Chris Wells

How many copies of a fixed odd cycle, $C_{2 m + 1}$ , can a planar graph contain? We answer this question asymptotically for $m \in {2, 3, 4}$ and prove a bound which is tight up to a fa…

math.CO2023★ 1 cited

On graphs embeddable in a layer of a hypercube and their extremal numbers

Maria Axenovich, Ryan R. Martin, Christian Winter

A graph is cubical if it is a subgraph of a hypercube. For a cubical graph $H$ and a hypercube $Q_{n}$ , $e x (Q_{n}, H)$ is the largest number of edges in an $H$ -free subgraph of $Q_{n}$ .…

math.CO2023

On the rainbow planar Turán number of paths

Ervin Győri, Ryan R. Martin, Addisu Paulos +2

An edge-colored graph is said to contain a rainbow- $F$ if it contains $F$ as a subgraph and every edge of $F$ is a distinct color. The problem of maximizing edges among $n$ -vertex…

math.CO2022

The Endomorphism Conjecture for Graded Posets of Width 4

Miklós Bóna, Ryan R. Martin

We prove the endomorphism conjecture for graded posets whose largest Whitney number is at most 4. In particular, this implies the endomorphism conjecture is true for graded posets…

math.CO2021★ 1 cited

Large Monochromatic Components of Small Diameter

Erik Carlson, Ryan R. Martin, Bo Peng +1

Gyárfás conjectured in 2011 that every $r$ -edge-colored $K_{n}$ contains a monochromatic component of bounded ("perhaps three") diameter on at least $n / (r - 1)$ vertices. Letzter prove…

math.CO2021

On generalized Turán results in height two posets

József Balogh, Ryan R. Martin, Dániel T. Nagy +1

For given posets $P$ and $Q$ and an integer $n$ , the generalized Turán problem for posets, asks for the maximum number of copies of $Q$ in a $P$ -free subset of the $n$ -dimensional…

math.CO2021

Accumulation points of the edit distance function

Christopher Cox, Ryan R. Martin, Daniel McGinnis

Given a hereditary property $H$ of graphs and some $p \in [0, 1]$ , the edit distance function $ed_{H} (p)$ is (asymptotically) the maximum proportion o…

math.CO2021

The maximum number of 10- and 12-cycles in a planar graph

Christopher Cox, Ryan R. Martin

For a fixed planar graph $H$ , let $N_{P} (n, H)$ denote the maximum number of copies of $H$ in an $n$ -vertex planar graph. In the case when $H$ is a…

math.CO2021★ 4 cited

Powers of Hamiltonian cycles in multipartite graphs

Louis DeBiasio, Ryan Martin, Theodore Molla

We prove that if $G$ is a $k$ -partite graph on $n$ vertices in which all of the parts have order at most $n / r$ and every vertex is adjacent to at least a $1 - 1/ r + o (1)$ proportion of…

math.CO2021

Graph clustering via generalized colorings

András London, Ryan R. Martin, András Pluhár

We propose a new approach for defining and searching clusters in graphs that represent real technological or transaction networks. In contrast to the standard way of finding dense…

math.CO2021

Counting paths, cycles and blow-ups in planar graphs

Christopher Cox, Ryan R. Martin

For a planar graph $H$ , let $N_{P} (n, H)$ denote the maximum number of copies of $H$ in an $n$ -vertex planar graph. In this paper, we prove that $\o…

math.CO2020

On the edit distance function of the random graph

Ryan R. Martin, Alexander W. N. Riasanovsky

Given a hereditary property of graphs $H$ and a $p \in [0, 1]$ , the edit distance function $ed_{H} (p)$ is asymptotically the maximum proportion of edge-addi…

math.CO2020

Splits with forbidden subgraphs

Maria Axenovich, Ryan R. Martin

In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be "split" such that the resulting graph is $H$ -free. Formally: A graph…

math.CO2020★ 1 cited

Planar Turán number of the 6-cycle

Debarun Ghosh, Ervin Győri, Ryan R. Martin +2

Let $ex_{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}_{\mat…

math.CO2020

The Maximum Number of Paths of Length Four in a Planar Graph

Debarun Ghosh, Ervin Győri, Ryan R. Martin +4

Let $f (n, H)$ denote the maximum number of copies of $H$ in an $n$ -vertex planar graph. The order of magnitude of $f (n, P_{k})$ , where $P_{k}$ is a path on $k$ vertices, is $n^{{\lfloor{…

math.CO2020★ 29 cited

Induced and non-induced poset saturation problems

Balázs Keszegh, Nathan Lemons, Ryan R. Martin +2

A subfamily $G \subseteq F \subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $F$ if there exists a bijection $i:P\rightarrow \ma…

math.CO2019

Improved bounds for induced poset saturation

Ryan R. Martin, Heather C. Smith, Shanise Walker

Given a finite poset $P$ , a family $F$ of elements in the Boolean lattice is induced- $P$ -saturated if $F$ contains no copy of $P$ …

math.CO2018

Counterexamples to a conjecture of Harris on Hall ratio

Adam Blumenthal, Bernard Lidicky, Ryan R. Martin +3

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 c…

math.CO2018★ 2 cited

Stability of the potential function

Catherine Erbes, Michael Ferrara, Ryan R. Martin +1

A graphic sequence $π$ is potentially $H$ -graphic if there is some realization of $π$ that contains $H$ as a subgraph. The Erdős-Jacobson-Lehel problem asks to determine $σ (H, n)$ ,…

math.CO2018★ 12 cited

On difference graphs and the local dimension of posets

Jinha Kim, Ryan R. Martin, Tomáš Masařík +4

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 vari…

math.CO2017★ 3 cited

A simple discharging method for forbidden subposet problems

Ryan R. Martin, Abhishek Methuku, Andrew Uzzell +1

The poset $Y_{k + 1, 2}$ consists of $k + 2$ distinct elements $x_{1}$ , $x_{2}$ , \dots, $x_{k}$ , $y_{1}$ , $y_{2}$ , such that $x_{1} \leq x_{2} \leq \dots \leq x_{k} \leq y_{1}$ ,~ $y_{2}$ . The poset $Y'_{k+1…

math.CO2017★ 4 cited

Polychromatic Colorings on the Integers

Maria Axenovich, John Goldwasser, Bernard Lidický +4

We show that for any set $S \subseteq Z$ , $∣ S ∣ = 4$ there exists a 3-coloring of $Z$ in which every translate of $S$ receives all three colors. This implies that $S$ …

math.CO2017

The Saturation Number of Induced Subposets of the Boolean Lattice

Michael Ferrara, Bill Kay, Lucas Kramer +4

Given a poset $P$ , a family $F$ of elements in the Boolean lattice is said to be $P$ -saturated if (1) $F$ contains no copy of $P$ as a subposet and (2) every proper superset of $F$ …

math.CO2016★ 5 cited

Polychromatic colorings of complete graphs with respect to 1-,2-factors and Hamiltonian cycles

Maria Axenovich, John Goldwasser, Ryan Hansen +5

If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polych…