Ruth Luo · wovepaper

activity

20162026

most citedOn

r

-uniform hypergraphs with circumference less than

r

19 citations · 59 across the 25 of their papers we have counts for

collaborators

30 papers

Covering complete $r$ -partite hypergraphs with few monochromatic components

Luke Hawranick, Ruth Luo

An edge-coloring of a hypergraph is {\em spanning} if every vertex sees every color used in the coloring. In this paper, we prove that for $k \geq 2 r \geq 6$ , in any spanning $k$ -c…

Ore's Theorem for rainbow Hamiltonian-connected graphs

Yupei Li, Ruth Luo

Let $G = (G_{1}, G_{2}, \dots, G_{m})$ be a collection of $m$ graphs on a common vertex set $V$ . For a graph $H$ with vertices in $V$ , we say that $G$ contains a rainbow $H$ if there is…

An Ore-type theorem for $[3]$ -graphs

Yupei Li, Linyuan Lu, Ruth Luo

Ore's Theorem states that if $G$ is an $n$ -vertex graph and every pair of non-adjacent vertices has degree sum at least $n$ , then $G$ is Hamiltonian. A $[3]$ -graph is a hypergraph…

Pancyclicity in hypergraphs with large uniformity

Teegan Bailey, Isaiah Hollars, Yupei Li +1

A Berge cycle of length $ℓ$ in a hypergraph $H$ is a sequence of alternating vertices and edges $v_{0} e_{0} v_{1} e_{1} ... v_{ℓ} e_{ℓ} v_{0}$ such that $\{v_i,v_{i+1}\}\subseteq…

Spectral radius and Hamiltonicity of uniform hypergraphs

George Brooks, William Linz, Ruth Luo

Let $n$ and $r$ be integers with $n - 2 \geq r \geq 3$ . We prove that any $r$ -uniform hypergraph $H$ on $n$ vertices with spectral radius $λ (H) > (r - 1 n - 2)$ mu…

Berge Pancyclic hypergraphs

Teegan Bailey, Yupei Li, Ruth Luo

A Berge cycle of length $ℓ$ in a hypergraph is an alternating sequence of $ℓ$ distinct vertices and $ℓ$ distinct edges $v_{1}, e_{1}, v_{2}, \dots, v_{ℓ}, e_{ℓ}$ such that $\…

Ore-type conditions for existence of a jellyfish in a graph

Jaehoon Kim, Alexandr Kostochka, Ruth Luo

The famous Dirac's Theorem states that for each $n \geq 3$ every $n$ -vertex graph $G$ with minimum degree $δ (G) \geq n /2$ has a hamiltonian cycle. When $δ (G) < n /2$ , this cannot be gu…

A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs, II: Large uniformities

Alexandr Kostochka, Ruth Luo, Grace McCourt

Dirac proved that each $n$ -vertex $2$ -connected graph with minimum degree $k$ contains a cycle of length at least $min {2 k, n}$ . We obtain analogous results for Berge cycles in h…

A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs

Alexandr Kostochka, Ruth Luo, Grace McCourt

Dirac proved that each $n$ -vertex $2$ -connected graph with minimum degree at least $k$ contains a cycle of length at least $min {2 k, n}$ . We consider a hypergraph version of this…

On a property of $2$ -connected graphs and Dirac's Theorem

Alexandr Kostochka, Ruth Luo, Grace McCourt

We refine a property of $2$ -connected graphs described in the classical paper of Dirac from 1952 and use the refined property to somewhat shorten Dirac's proof of the fact that eac…

Minimum degree ensuring that a hypergraph is hamiltonian-connected

Alexandr Kostochka, Ruth Luo, Grace McCourt

A hypergraph $H$ is hamiltonian-connected if for any distinct vertices $x$ and $y$ , $H$ contains a hamiltonian Berge path from $x$ to $y$ . We find for all $3 \leq r < n$ , exact lower…

Dirac's Theorem for hamiltonian Berge cycles in uniform hypergraphs

Alexandr Kostochka, Ruth Luo, Grace McCourt

The famous Dirac's Theorem gives an exact bound on the minimum degree of an $n$ -vertex graph guaranteeing the existence of a hamiltonian cycle. We prove exact bounds of similar typ…

Large monochromatic components in almost complete graphs and bipartite graphs

Zoltan Furedi, Ruth Luo

Gyárfas proved that every coloring of the edges of $K_{n}$ with $t + 1$ colors contains a monochromatic connected component of size at least $n / t$ . Later, Gyárfás and Sárközy asked for…

Forbidding $K_{2, t}$ traces in triple systems

Ruth Luo, Sam Spiro

Let $H$ and $F$ be hypergraphs. We say $H$ contains $F$ as a trace if there exists some set $S \subseteq V (H)$ such that $H ∣_{S} := {E \cap S : E \in E (H)}$ contains a subhypergraph is…

Conditions for a bigraph to be super-cyclic

Alexandr Kostochka, Mikhail Lavrov, Ruth Luo +1

A hypergraph $H$ is super-pancyclic if for each $A \subseteq V (H)$ with $∣ A ∣ \geq 3$ , $H$ contains a Berge cycle with base vertex set $A$ . We present two…

Longest cycles in 3-connected hypergraphs and bipartite graphs

Alexandr Kostochka, Mikhail Lavrov, Ruth Luo +1

In the language of hypergraphs, our main result is a Dirac-type bound: we prove that every $3$ -connected hypergraph $H$ with $δ (H) \geq max {∣ V (H) ∣, \frac{∣ E ( H ) ∣ + 10}{4}}$ has a h…

math.CO2020★ 1 cited

Induced Turán problems and traces of hypergraphs

Zoltan Furedi, Ruth Luo

Let $F$ be a graph. We say that a hypergraph $H$ contains an induced Berge $F$ if the vertices of $F$ can be embedded to $H$ (e.g., $V (F) \subseteq V (H)$ ) and there exists an inject…

math.CO2020★ 2 cited

Berge cycles in non-uniform hypergraphs

Zoltan Furedi, Alexandr Kostochka, Ruth Luo

We consider two extremal problems for set systems without long Berge cycles. First we give Dirac-type minimum degree conditions that force long Berge cycles. Next we give an upper…

math.CO2020★ 2 cited

Towards the Small Quasi-Kernel Conjecture

Alexandr Kostochka, Ruth Luo, Songling Shan

Let $D = (V, A)$ be a digraph. A vertex set $K \subseteq V$ is a quasi-kernel of $D$ if $K$ is an independent set in $D$ and for every vertex $v \in V ∖ K$ , $v$ is at most distan…

Super-pancyclic hypergraphs and bipartite graphs

Alexandr Kostochka, Ruth Luo, Dara Zirlin

We find Dirac-type sufficient conditions for a hypergraph $H$ with few edges to be hamiltonian. We also show that these conditions provide that $H$ is {\em super-…

math.CO2019★ 1 cited

On 2-connected hypergraphs with no long cycles

Zoltan Furedi, Alexandr Kostochka, Ruth Luo

We give an upper bound for the maximum number of edges in an $n$ -vertex 2-connected $r$ -uniform hypergraph with no Berge cycle of length $k$ or greater, where $n\geq k \geq 4r\geq…

math.CO2018★ 14 cited

Avoiding long Berge cycles II, exact bounds for all $n$

Zoltan Furedi, Alexandr Kostochka, Ruth Luo

Let $E G_{r} (n, k)$ denote the maximum number of edges in an $n$ -vertex $r$ -uniform hypergraph with no Berge cycles of length $k$ or longer. In the first part of this work, we have fou…

math.CO2018★ 19 cited

On $r$ -uniform hypergraphs with circumference less than $r$

Alexandr Kostochka, Ruth Luo

We show that for each $k \geq 4$ and $n > r \geq k + 1$ , every $n$ -vertex $r$ -uniform hypergraph with no Berge cycle of length at least $k$ has at most $\frac{( k - 1 ) ( n - 1 )}{r}$ edges. The…

math.CO2018★ 11 cited

Avoiding long Berge cycles

Zoltan Furedi, Alexandr Kostochka, Ruth Luo

Let $n \geq k \geq r + 3$ and $H$ be an $n$ -vertex $r$ -uniform hypergraph. We show that if $∣ H ∣ > \frac{n - 1}{k - 2} (r k - 1)$ then $H$ contains a Berge cyc…