Source author record

Xihe Li

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

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Integer colorings with no rainbow 3-term arithmetic progression

In this paper, we study the rainbow Erdős-Rothschild problem with respect to 3-term arithmetic progressions. We obtain the asymptotic number of $r$ -colorings of $[n]$ without rainbow 3-term arithmetic progressions, and we show that the typical colorings with this property are 2-colorings. We also prove that $[n]$ attains the maximum number of rainbow 3-term arithmetic progression-free $r$ -colorings among all subsets of $[n]$ . Moreover, the exact number of rainbow 3-term arithmetic progression-free $r$ -colorings of $\mathbb{Z}_p$ is obtained, where $p$ is any prime and $\mathbb{Z}_p$ is the cyclic group of order $p$ .

preprint2021arXiv

Extremal problems and results related to Gallai-colorings

A Gallai-coloring (Gallai- $k$ -coloring) is an edge-coloring (with colors from $\{1, 2, \ldots, k\}$ ) of a complete graph without rainbow triangles. Given a graph $H$ and a positive integer $k$ , the $k$ -colored Gallai-Ramsey number $GR_k(H)$ is the minimum integer $n$ such that every Gallai- $k$ -coloring of the complete graph $K_n$ contains a monochromatic copy of $H$ . In this paper, we consider two extremal problems related to Gallai- $k$ -colorings. First, we determine upper and lower bounds for the maximum number of edges that are not contained in any rainbow triangle or monochromatic triangle in a $k$ -edge-coloring of $K_n$ . Second, for $n\geq GR_k(K_3)$ , we determine upper and lower bounds for the minimum number of monochromatic triangles in a Gallai- $k$ -coloring of $K_{n}$ , yielding the exact value for $k=3$ . Furthermore, we determine the Gallai-Ramsey number $GR_k(K_4+e)$ for the graph on five vertices consisting of a $K_4$ with a pendant edge.

preprint2021arXiv

The Erdős-Gyárfás function with respect to Gallai-colorings

For fixed $p$ and $q$ , an edge-coloring of the complete graph $K_n$ is said to be a $(p, q)$ -coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n, p, q)$ is the minimum number of colors needed for $K_n$ to have a $(p, q)$ -coloring. This function was introduced about 45 years ago, but was studied systematically by Erdős and Gyárfás in 1997, and is now known as the Erdős-Gyárfás function. In this paper, we study $f(n, p, q)$ with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of $K_n$ without rainbow triangles. Combining the two concepts, we consider the function $g(n, p, q)$ that is the minimum number of colors needed for a Gallai- $(p, q)$ -coloring of $K_n$ . Using the anti-Ramsey number for $K_3$ , we have that $g(n, p, q)$ is nontrivial only for $2\leq q\leq p-1$ . We give a general lower bound for this function and we study how this function falls off from being equal to $n-1$ when $q=p-1$ and $p\geq 4$ to being $Θ(\log n)$ when $q = 2$ . In particular, for appropriate $p$ and $n$ , we prove that $g=n-c$ when $q=p-c$ and $c\in \{1,2\}$ , $g$ is at most a fractional power of $n$ when $q=\lfloor\sqrt{p-1}\rfloor$ , and $g$ is logarithmic in $n$ when $2\leq q\leq \lfloor\log_2 (p-1)\rfloor+1$ .

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.