Allan Lo
YOU?
Author Swipe
View article: Powers of Hamilton cycles in oriented and directed graphs
Powers of Hamilton cycles in oriented and directed graphs Open
The Pósa–Seymour conjecture determines the minimum degree threshold for forcing the $k$ th power of a Hamilton cycle in a graph. After numerous partial results, Komlós, Sárközy, and Szemerédi proved the conjecture for sufficiently large gr…
View article: From finding a spanning subgraph $H$ to an $H$-factor
From finding a spanning subgraph $H$ to an $H$-factor Open
A typical Dirac-type problem in extremal graph theory is to determine the minimum degree threshold for a graph $G$ to have a spanning subgraph $H$, e.g. the Dirac theorem. A natural following up problem would be to seek an $H$-factor, whic…
View article: Polynomial Bounds for Monochromatic Tight Cycle Partition in $r$-Edge-Coloured $K_n^{(k)}$
Polynomial Bounds for Monochromatic Tight Cycle Partition in $r$-Edge-Coloured $K_n^{(k)}$ Open
Let $K_n^{(k)}$ be the complete $k$-graph on $n$ vertices. A $k$-uniform tight cycle is a $k$-graph with its vertices cyclically ordered so that every $k$ consecutive vertices form an edge and any two consecutive edges share exactly $k-1$ …
View article: Embedding loose trees in $k$-uniform hypergraphs
Embedding loose trees in $k$-uniform hypergraphs Open
A classical result of Komlós, Sárközy and Szemerédi shows that every large $n$-vertex graph with minimum degree at least $(1/2+γ)n$ contains all spanning trees of bounded degree. We generalised this result to loose spanning hypertrees in $…
View article: Cycle Partitions in Dense Regular Digraphs and Oriented Graphs
Cycle Partitions in Dense Regular Digraphs and Oriented Graphs Open
A conjecture of Jackson from 1981 states that every d -regular oriented graph on n vertices with $n\leq 4d+1$ is Hamiltonian. We prove this conjecture for sufficiently large n . In fact we prove a more general result that for all $\alpha>0…
View article: Powers of Hamilton cycles in oriented and directed graphs
Powers of Hamilton cycles in oriented and directed graphs Open
The Pósa--Seymour conjecture determines the minimum degree threshold for forcing the $k$th power of a Hamilton cycle in a graph. After numerous partial results, Komlós, Sárközy and Szemerédi proved the conjecture for sufficiently large gra…
View article: Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree
Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree Open
In 1975 Bollobás, Erdős, and Szemerédi asked what minimum degree guarantees an octahedral subgraph $K_3(2)$ in any tripartite graph $G$ with $n$ vertices in each vertex class. We show that $δ(G)\geq n+2n^{\frac{5}{6}}$ suffices thus improv…
View article: Simultaneous edge-colourings
Simultaneous edge-colourings Open
We study a generalisation of Vizing's theorem, where the goal is to simultaneously colour the edges of graphs $G_1,\dots,G_k$ with few colours. We obtain asymptotically optimal bounds for the required number of colours in terms of the maxi…
View article: Polynomial bounds for monochromatic tight cycle partition in $r$-edge-coloured $K_n^{(k)}$
Polynomial bounds for monochromatic tight cycle partition in $r$-edge-coloured $K_n^{(k)}$ Open
Let $K_n^{(k)}$ be the complete $k$-graph on $n$ vertices. A $k$-uniform tight cycle is a $k$-graph with its vertices cyclically ordered so that every $k$ consecutive vertices form an edge and any two consecutive edges share exactly $k-1$ …
View article: Towards an edge-coloured Corrádi--Hajnal theorem
Towards an edge-coloured Corrádi--Hajnal theorem Open
A classical result of Corrádi and Hajnal states that every graph $G$ on $n$ vertices with $n\in 3\mathbb{N}$ and $δ(G) \ge 2n/3$ contains a perfect triangle-tiling, i.e.,\ a spanning set of vertex-disjoint triangles. We explore a generalis…
View article: A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs
A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs Open
The r-color size-Ramsey number of a k-uniform hypergraph H, denoted by Rˆr(H), is the minimum number of edges in a k-uniform hypergraph G such that for every r-coloring of the edges of G there exists a monochromatic copy of H. In the case …
View article: Cycle decompositions in k-uniform hypergraphs
Cycle decompositions in k-uniform hypergraphs Open
We show that k-uniform hypergraphs on n vertices whose codegree is at least (2/3+o(1))n can be decomposed into tight cycles, subject to the trivial divisibility conditions. As a corollary, we show those graphs contain tight Euler tours as …
View article: Ramsey goodness of $k$-uniform paths, or the lack thereof
Ramsey goodness of $k$-uniform paths, or the lack thereof Open
Given a pair of $k$-uniform hypergraphs $(G,H)$, the Ramsey number of $(G,H)$, denoted by $R(G,H)$, is the smallest integer $n$ such that in every red/blue-colouring of the edges of $K_n^{(k)}$ there exists a red copy of $G$ or a blue copy…
View article: Hamilton cycles in dense regular digraphs and oriented graphs
Hamilton cycles in dense regular digraphs and oriented graphs Open
We prove that for every ε>0 there exists n0=n0(ε) such that every regular oriented graph on n>n0 vertices and degree at least (1/4+ε)n has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We a…
View article: Cycle Partitions in Dense Regular Digraphs and Oriented Graphs
Cycle Partitions in Dense Regular Digraphs and Oriented Graphs Open
A conjecture of Jackson from 1981 states that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian. We prove this conjecture for sufficiently large $n$. In fact we prove a more general result that for all $α>0$…
View article: Almost partitioning every $2$-edge-coloured complete $k$-graph into $k$ monochromatic tight cycles
Almost partitioning every $2$-edge-coloured complete $k$-graph into $k$ monochromatic tight cycles Open
A $k$-uniform tight cycle is a $k$-graph with a cyclic order of its vertices such that every $k$ consecutive vertices from an edge. We show that for $k\geq 3$, every red-blue edge-coloured complete $k$-graph on $n$ vertices contains $k$ ve…
View article: A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs
A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs Open
The $r$-color size-Ramsey number of a $k$-uniform hypergraph $H$, denoted by $\hat{R}_r(H)$, is the minimum number of edges in a $k$-uniform hypergraph $G$ such that for every $r$-coloring of the edges of $G$ there exists a monochromatic c…
View article: Path decompositions of tournaments
Path decompositions of tournaments Open
In 1976, Alspach, Mason, and Pullman conjectured that any tournament 𝑇of even order can be decomposed into exactly ex(𝑇)paths, where ex(𝑇)∶=12∑𝑣∈𝑉(𝑇)|𝑑+𝑇(𝑣) −𝑑−𝑇(𝑣)|. We prove this conjecture for all sufficiently large tournaments. We also…
View article: Towards Lehel's Conjecture for 4-Uniform Tight Cycles
Towards Lehel's Conjecture for 4-Uniform Tight Cycles Open
A $k$-uniform tight cycle is a $k$-uniform hypergraph with a cyclic ordering of its vertices such that its edges are all the sets of size $k$ formed by $k$ consecutive vertices in the ordering.We prove that every red-blue edge-coloured $K_…
View article: Cycle Partition of Dense Regular Digraphs and Oriented Graphs
Cycle Partition of Dense Regular Digraphs and Oriented Graphs Open
Magnant and Martin~\cite{PathCover} conjectured that every $d$-regular graph on $n$ vertices can be covered by $n/(d+1)$ vertex-disjoint paths. Gruslys and Letzter~\cite{GruslysLetzter} verified this conjecture in the dense case, even for …
View article: Almost partitioning every 2-edge-coloured complete k-graph into k monochromatic tight cycles
Almost partitioning every 2-edge-coloured complete k-graph into k monochromatic tight cycles Open
A $k$-uniform tight cycle is a $k$-graph with a cyclic order of its vertices such that every~$k$ consecutive vertices from an edge. We show that for $k\geq 3$, every red-blue edge-coloured complete $k$-graph on~$n$ vertices contains~$k$ ve…
View article: Tight path, what is it (Ramsey-)good for? Absolutely (almost) nothing!
Tight path, what is it (Ramsey-)good for? Absolutely (almost) nothing! Open
Given a pair of~$k$-uniform hypergraphs~$(G,H)$, the \emph{Ramsey number} of~$(G,H)$, denoted by~$R(G,H)$, is the smallest integer~$n$ such that in every red/blue-colouring of the edges of~$K_n^{(k)}$ there exists a red copy of~$G$ or a bl…
View article: An oriented discrepancy version of Dirac's theorem
An oriented discrepancy version of Dirac's theorem Open
The study of graph discrepancy problems, initiated by Erdős in the 1960s, has received renewed attention in recent years. In general, given a $2$-edge-coloured graph $G$, one is interested in embedding a copy of a graph $H$ in $G$ with lar…
View article: Cycle decompositions in $k$-uniform hypergraphs
Cycle decompositions in $k$-uniform hypergraphs Open
We show that $k$-uniform hypergraphs on $n$ vertices whose codegree is at least $(2/3 + o(1))n$ can be decomposed into tight cycles, subject to the trivial divisibility conditions. As a corollary, we show those graphs contain tight Euler t…
View article: Complete subgraphs in a multipartite graph
Complete subgraphs in a multipartite graph Open
In 1975 Bollobás, Erdős, and Szemerédi asked the following question: given positive integers $n, t, r$ with $2\le t\le r-1$ , what is the largest minimum degree $\delta (G)$ among all $r$ -partite graphs $G$ with parts of size $n$ and whic…
View article: Hamilton Cycles in Dense Regular Digraphs and Oriented Graphs
Hamilton Cycles in Dense Regular Digraphs and Oriented Graphs Open
We prove that for every $\varepsilon > 0$ there exists $n_0=n_0(\varepsilon)$ such that every regular oriented graph on $n > n_0$ vertices and degree at least $(1/4 + \varepsilon)n$ has a Hamilton cycle. This establishes an approximate ver…
View article: Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs
Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs Open
The upper density of an infinite graph $G$ with $V(G) \subseteq \mathbb{N}$ is defined as $\overline{d}(G) = \limsup_{n \rightarrow \infty}{|V(G) \cap \{1,\ldots,n\}|}/{n}$. Let $K_{\mathbb{N}}$ be the infinite complete graph with vertex s…
View article: The Ramsey number for 4-uniform tight cycles
The Ramsey number for 4-uniform tight cycles Open
A $k$-uniform tight cycle is a $k$-graph with a cyclic ordering of its vertices such that its edges are precisely the sets of $k$ consecutive vertices in that ordering. A $k$-uniform tight path is a $k$-graph obtained by deleting a vertex …