Source author record

Xiaofan Yuan

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

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

4-Separations in Hajós Graphs

As a natural extension of the Four Color Theorem, Hajós conjectured that graphs containing no $K_5$ -subdivision are 4-colorable. Any possible counterexample to this conjecture with minimum number of vertices is called a {\it Hajós graph}. Previous results show that Hajós graphs are 4-connected but not 5-connected. A $k$ -separation in a graph $G$ is a pair $(G_1,G_2)$ of edge-disjoint subgraphs of $G$ such that $|V(G_1\cap G_2)|=k$ , $G=G_1\cup G_2$ , and $G_i\not\subseteq G_{3-i}$ for $i=1,2$ . In this paper, we show that Hajós graphs do not admit a 4-separation $(G_1,G_2)$ such that $|V(G_1)|\ge 6$ and $G_1$ can be drawn in the plane with no edge crossings and all vertices in $V(G_1\cap G_2)$ incident with a common face. This is a step in our attempt to reduce Hajós' conjecture to the Four Color Theorem.

preprint2020arXiv

Rainbow matchings for 3-uniform hypergraphs

Kühn, Osthus, and Treglown and, independently, Khan proved that if $H$ is a $3$ -uniform hypergraph with $n$ vertices such that $n\in 3\mathbb{Z}$ and large, and $δ_1(H)>{n-1\choose 2}-{2n/3\choose 2}$ , then $H$ contains a perfect matching. In this paper, we show that for $n\in 3\mathbb{Z}$ sufficiently large, if $F_1, \ldots, F_{n/3}$ are 3-uniform hypergrapghs with a common vertex set and $δ_1(F_i)>{n-1\choose 2}-{2n/3\choose 2}$ for $i\in [n/3]$ , then $\{F_1,\dots, F_{n/3}\}$ admits a rainbow matching, i.e., a matching consisting of one edge from each $F_i$ . This is done by converting the rainbow matching problem to a perfect matching problem in a special class of uniform hypergraphs.

preprint2016arXiv

Some extremal results on complete degenerate hypergraphs

Let $K^{(r)}_{s_1,s_2,\cdots,s_r}$ be the complete $r$ -partite $r$ -uniform hypergraph and $ex(n,K^{(r)}_{s_1,s_2,\cdots,s_r})$ be the maximum number of edges in any $n$ -vertex $K^{(r)}_{s_1,s_2,\cdots,s_r}$ -free $r$ -uniform hypergraph. It is well-known in the graph case that $ex(n,K_{s,t})=Θ(n^{2-1/s})$ when $t$ is sufficiently larger than $s$ . In this note, we generalize the above to hypergraphs by showing that if $s_r$ is sufficiently larger than $s_1,s_2,\cdots,s_{r-1}$ then $ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})=Θ\left(n^{r-\frac{1}{s_1s_2\cdots s_{r-1}}}\right).$ This follows from a more general Turán type result we establish in hypergraphs, which also improves and generalizes some recent results of Alon and Shikhelman. The lower bounds of our results are obtained by the powerful random algebraic method of Bukh. Another new, perhaps unsurprising insight which we provide here is that one can also use the random algebraic method to construct non-degenerate (hyper-)graphs for various Turán type problems. The asymptotics for $ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})$ is also proved by Verstraëte independently with a different approach.

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.