Source author record

Ta Sheng Tan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

8works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Burnability of Double Spiders and Path Forests

The burning number of a graph can be used to measure the spreading speed of contagion in a network. The burning number conjecture is arguably the main unresolved conjecture related to this graph parameter, which can be settled by showing that every tree of order $m^2$ has burning number at most $m$ . This is known to hold for many classes of trees, including spiders - trees with exactly one vertex of degree greater than two. In fact, it has been verified that certain spiders of order slightly larger than $m^2$ also have burning numbers at most $m$ , a result that has then been conjectured to be true for all trees. The first focus of this paper is to verify this slightly stronger conjecture for double spiders - trees with two vertices of degrees at least three and they are adjacent. Our other focus concerns the burning numbers of path forests, a class of graphs in which their burning numbers are naturally related to that of spiders and double spiders. Here, our main result shows that a path forest of order $m^2$ with a sufficiently long shortest path has burning number exactly $m$ , the smallest possible for any path forest of the same order.

preprint2016arXiv

Tiling with arbitrary tiles

Let $T$ be a tile in $\mathbb{Z}^n$ , meaning a finite subset of $\mathbb{Z}^n$ . It may or may not tile $\mathbb{Z}^n$ , in the sense of $\mathbb{Z}^n$ having a partition into copies of $T$ . However, we prove that $T$ does tile $\mathbb{Z}^d$ for some $d$ . This resolves a conjecture of Chalcraft.

preprint2014arXiv

Connected Colourings of Complete Graphs and Hypergraphs

Gallai's colouring theorem states that if the edges of a complete graph are 3-coloured, with each colour class forming a connected (spanning) subgraph, then there is a triangle that has all 3 colours. What happens for more colours: if we $k$ -colour the edges of the complete graph, with each colour class connected, how many of the $\binom{k}{3}$ triples of colours must appear as triangles? In this note we show that the `obvious' conjecture, namely that there are always at least $\binom{k-1}{2}$ triples, is not correct. We determine the minimum asymptotically. This answers a question of Johnson. We also give some results about the analogous problem for hypergraphs, and we make a conjecture that we believe is the `right' generalisation of Gallai's theorem to hypergraphs.

preprint2014arXiv

Cycles in Oriented 3-graphs

An oriented 3-graph consists of a family of triples (3-sets), each of which is given one of its two possible cyclic orientations. A cycle in an oriented 3-graph is a positive sum of some of the triples that gives weight zero to each 2-set. Our aim in this paper is to consider the following question: how large can the girth of an oriented 3-graph (on $n$ vertices) be? We show that there exist oriented 3-graphs whose shortest cycle has length $\frac{n^2}{2}(1+o(1))$ : this is asymptotically best possible. We also show that there exist 3-tournaments whose shortest cycle has length $\frac{n^2}{3}(1+o(1))$ , in complete contrast to the case of 2-tournaments.

preprint2012arXiv

A note on large rainbow matchings in edge-coloured graphs

A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on $n$ vertices with minimum colour degree at least $k$ contains a rainbow matching of size at least $k$ , provided $n\geq (17/4)k^2$ . In this paper, we show that $n\geq 4k-4$ is sufficient for $k \ge 4$ .

preprint2010arXiv

The Brush Number of the Two-Dimensional Torus

In this paper we are interested in the brush number of a graph - a concept introduced by McKeil and by Messinger, Nowakowski and Pralat. Our main aim in this paper is to determine the brush number of the two-dimensional torus. This answers a question of Bonato and Messinger. We also find the brush number of the cartesian product of a clique with a path, which is related to the Box Cleaning Conjecture of Bonato and Messinger.

preprint2010arXiv

Traces Without Maximal Chains

The trace of a family of sets $\mathcal{A}$ on a set $X$ is $\mathcal{A}|_X=\{A\cap X:A\in \mathcal{A}\}$ . If $\mathcal{A}$ is a family of $k$ -sets from an $n$ -set such that for any $r$ -subset $X$ the trace $\mathcal{A}|_X$ does not contain a maximal chain, then how large can $\mathcal{A}$ be? Patkós conjectured that, for $n$ sufficiently large, the size of $\mathcal{A}$ is at most $\binom{n-k+r-1}{r-1}$ . Our aim in this paper is to prove this conjecture.

preprint2009arXiv

Directed Simplices In Higher Order Tournaments

It is well known that a tournament (complete oriented graph) on $n$ vertices has at most ${1/4}\binom{n}{3}$ directed triangles, and that the constant 1/4 is best possible. Motivated by some geometric considerations, our aim in this paper is to consider some `higher order' versions of this statement. For example, if we give each 3-set from an $n$ -set a cyclic ordering, then what is the greatest number of `directed 4-sets' we can have? We give an asymptotically best possible answer to this question, and give bounds in the general case when we orient each $d$ -set from an $n$ -set.

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.