BZPEER

preprint2021arXiv

Large book--cycle Ramsey numbers

Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all sharing a common $K_k$ , and let $C_m$ be a cycle of length $m$ . In this paper, we first determine the exact value of $r(B_n^{(2)}, C_m)$ for $\frac{8}{9}n+112\le m\le \lceil\frac{3n}{2}\rceil+1$ and $n \geq 1000$ . This answers a question of Faudree, Rousseau and Sheehan (Cycle--book Ramsey numbers, {\it Ars Combin.,} {\bf 31} (1991), 239--248) in a stronger form when $m$ and $n$ are large. Building upon this exact result, we are able to determine the asymptotic value of $r(B_n^{(k)}, C_n)$ for each $k \geq 3$ . Namely, we prove that for each $k \geq 3$ , $r(B_n^{(k)}, C_n)= (k+1+o_k(1))n.$ This extends a result due to Rousseau and Sheehan (A class of Ramsey problems involving trees, {\it J.~London Math.~Soc.,} {\bf 18} (1978), 392--396).

preprint2018arXiv

Extensions of Erdős-Gallai Theorem and Luo's Theorem with Applications

The famous Erdős-Gallai Theorem on the Turán number of paths states that every graph with $n$ vertices and $m$ edges contains a path with at least $\frac{2m}{n}$ edges. In this note, we first establish a simple but novel extension of the Erdős-Gallai Theorem by proving that every graph $G$ contains a path with at least $\frac{(s+1)N_{s+1}(G)}{N_{s}(G)}+s-1$ edges, where $N_j(G)$ denotes the number of $j$ -cliques in $G$ for $1\leq j\leqω(G)$ . We also construct a family of graphs which shows our extension improves the estimate given by Erdős-Gallai Theorem. Among applications, we show, for example, that the main results of \cite{L17}, which are on the maximum possible number of $s$ -cliques in an $n$ -vertex graph without a path with $l$ vertices (and without cycles of length at least $c$ ), can be easily deduced from this extension. Indeed, to prove these results, Luo \cite{L17} generalized a classical theorem of Kopylov and established a tight upper bound on the number of $s$ -cliques in an $n$ -vertex 2-connected graph with circumference less than $c$ . We prove a similar result for an $n$ -vertex 2-connected graph with circumference less than $c$ and large minimum degree. We conclude this paper with an application of our results to a problem from spectral extremal graph theory on consecutive lengths of cycles in graphs.

preprint2016arXiv

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the {\em principal ratio}, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on $n$ vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.

preprint2015arXiv

A path Turan problem for infinite graphs

Let $G$ be an infinite graph whose vertex set is the set of positive integers, and let $G_n$ be the subgraph of $G$ induced by the vertices $\{1,2, \dots , n \}$ . An increasing path of length $k$ in $G$ , denoted $I_k$ , is a sequence of $k+1$ vertices $1 \leq i_1 < i_2 < \dots < i_{k+1}$ such that $i_1, i_2, \ldots, i_{k+1}$ is a path in $G$ . For $k \geq 2$ , let $p(k)$ be the supremum of $\liminf_{ n \rightarrow \infty} \frac{ e(G_n) }{n^2}$ over all $I_k$ -free graphs $G$ . In 1962, Czipszer, Erdős, and Hajnal proved that $p(k) = \frac{1}{4} (1 - \frac{1}{k})$ for $k \in \{2,3 \}$ . Erdős conjectured that this holds for all $k \geq 4$ . This was disproved for certain values of $k$ by Dudek and Rödl who showed that $p(16) > \frac{1}{4} (1 - \frac{1}{16})$ and $p(k) > \frac{1}{4} + \frac{1}{200}$ for all $k \geq 162$ . Given that the conjecture of Erdős is true for $k \in \{2,3 \}$ but false for large $k$ , it is natural to ask for the smallest value of $k$ for which $p(k) > \frac{1}{4} ( 1 - \frac{1}{k} )$ . In particular, the question of whether or not $p(4) = \frac{1}{4} ( 1 - \frac{1}{4} )$ was mentioned by Dudek and Rödl as an open problem. We solve this problem by proving that $p(4) \geq \frac{1}{4} (1 - \frac{1}{4} ) + \frac{1}{584064}$ and $p(k) > \frac{1}{4} (1 - \frac{1}{k})$ for $4 \leq k \leq 15$ . We also show that $p(4) \leq \frac{1}{4}$ which improves upon the previously best known upper bound on $p(4)$ . Therefore, $p(4)$ must lie somewhere between $\frac{3}{16} + \frac{1}{584064}$ and $\frac{1}{4}$

preprint2015arXiv

Decomposition of random graphs into complete bipartite graphs

We consider the problem of partitioning the edge set of a graph $G$ into the minimum number $τ(G)$ of edge-disjoint complete bipartite subgraphs. We show that for a random graph $G$ in $G(n,p)$ , for $p$ is a constant no greater than $1/2$ , almost surely $τ(G)$ is between $n- c(\ln_{1/p} n)^{3+ε}$ and $n - 2\ln_{1/(1-p)} n$ for any positive constants $c$ and $ε$ .

preprint2015arXiv

On the decomposition of random hypergraphs

For an $r$ -uniform hypergraph $H$ , let $f(H)$ be the minimum number of complete $r$ -partite $r$ -uniform subhypergraphs of $H$ whose edge sets partition the edge set of $H$ . For a graph $G$ , $f(G)$ is the bipartition number of $G$ which was introduced by Graham and Pollak in 1971. In 1988, Erdős conjectured that if $G \in G(n,1/2)$ , then with high probability $f(G)=n-α(G)$ , where $α(G)$ is the independence number of $G$ . This conjecture and related problems have received a lot of attention recently. In this paper, we study the value of $f(H)$ for a typical $r$ -uniform hypergraph $H$ . More precisely, we prove that if $(\log n)^{2.001}/n \leq p \leq 1/2$ and $H \in H^{(r)}(n,p)$ , then with high probability $f(H)=(1-π(K^{(r-1)}_r)+o(1))\binom{n}{r-1}$ , where $π(K^{(r-1)}_r)$ is the Turán density of $K^{(r-1)}_r$ .

preprint2015arXiv

The Ramsey number of generalized loose paths in uniform Hypergrpahs

Let $H=(V,E)$ be an $r$ -uniform hypergraph. For each $1 \leq s \leq r-1$ , an $s$ -path ${\mathcal P}^{r,s}_n$ of length $n$ in $H$ is a sequence of distinct vertices $v_1,v_2,\ldots,v_{s+n(r-s)}$ such that $\{v_{1+i(r-s)},\ldots, v_{s+(i+1)(r-s)}\}\in E(H)$ for each $0 \leq i \leq n-1$ .Recently, the Ramsey number of $1$ -paths in uniform hypergraphs has received a lot of attention. In this paper, we consider the Ramsey number of $r/2-$ paths for even $r$ . Namely, we prove the following exact result: $R({\mathcal P}^{r,r/2}_n,{\mathcal P}^{r,r/2}_3)=R({\mathcal P}^{r,r/2}_n,{\mathcal P}^{r,r/2}_4)=\tfrac{(n+1)r}{2}+1.$

preprint2014arXiv

On the chromatic number of the Erdős-Rényi orthogonal polarity graph

For a prime power $q$ , let $ER_q$ denote the Erdős-Rényi orthogonal polarity graph. We prove that if $q$ is an even power of an odd prime, then $χ( ER_{q}) \leq 2 \sqrt{q} + O ( \sqrt{q} / \log q)$ . This upper bound is best possible up to a constant factor of at most 2. If $q$ is an odd power of an odd prime and satisfies some condition on irreducible polynomials, then we improve the best known upper bound for $χ(ER_{q})$ substantially. We also show that for sufficiently large $q$ , every $ER_q$ contains a subgraph that is not 3-chromatic and has at most 36 vertices.

preprint2013arXiv

Bounds for generalized Sidon sets

Let $Γ$ be an abelian group and $g \geq h \geq 2$ be integers. A set $A \subset Γ$ is a $C_h[g]$ -set if given any set $X \subset Γ$ with $|X| = k$ , and any set $\{ k_1 , \dots , k_g \} \subset Γ$ , at least one of the translates $X+ k_i$ is not contained in $A$ . For any $g \geq h \geq 2$ , we prove that if $A \subset \{1,2, \dots ,n \}$ is a $C_h[g]$ -set in $\mathbb{Z}$ , then $|A| \leq (g-1)^{1/h} n^{1 - 1/h} + O(n^{1/2 - 1/2h})$ . We show that for any integer $n \geq 1$ , there is a $C_3 [3]$ -set $A \subset \{1,2, \dots , n \}$ with $|A| \geq (4^{-2/3} + o(1)) n^{2/3}$ . We also show that for any odd prime $p$ , there is a $C_3[3]$ -set $A \subset \mathbb{F}_p^3$ with $|A| \geq p^2 - p$ , which is asymptotically best possible. Using the projective norm graphs from extremal graph theory, we show that for each integer $h \geq 3$ , there is a $C_h[h! +1]$ -set $A \subset \{1,2, \dots , n \}$ with $|A| \geq ( c_h +o(1))n^{1-1/h}$ . A set $A$ is a \emph{weak $C_h[g]$ -set} if we add the condition that the translates $X +k_1, \dots , X + k_g$ are all pairwise disjoint. We use the probabilistic method to construct weak $C_h[g]$ -sets in $\{1,2, \dots , n \}$ for any $g \geq h \geq 2$ . Lastly we obtain upper bounds on infinite $C_h[g]$ -sequences. We prove that for any infinite $C_h[g$ ]-sequence $A \subset \mathbb{N}$ , we have $A(n) = O ( n^{1 - 1/h} ( \log n )^{ - 1/h} )$ for infinitely many $n$ , where $A(n) = | A \cap \{1,2, \dots , n \}|$ .

preprint2013arXiv

Infinite Turán problems for bipartite graphs

We consider an infinite version of the bipartite Turán problem. Let $G$ be an infinite graph with $V(G) = \mathbb{N}$ and let $G_n$ be the $n$ -vertex subgraph of $G$ induced by the vertices $\{1,2, \dots, n \}$ . We show that if $G$ is $K_{2,t+1}$ -free then for infinitely many $n$ , $e(G_n) \leq 0.471 \sqrt{t} n^{3/2}$ . Using the $K_{2,t+1}$ -free graphs constructed by Füredi, we construct an infinite $K_{2,t+1}$ -free graph with $e(G_n) \geq 0.23 \sqrt{t}n^{3/2}$ for all $n \geq n_0$ .

preprint2012arXiv

Spectra of edge-independent random graphs

Let $G$ be a random graph on the vertex set $\{1,2,..., n\}$ such that edges in $G$ are determined by independent random indicator variables, while the probability $p_{ij}$ for $\{i,j\}$ being an edge in $G$ is not assumed to be equal. Spectra of the adjacency matrix and the normalized Laplacian matrix of $G$ are recently studied by Oliveira and Chung-Radcliffe. Let $A$ be the adjacency matrix of $G$ , $\bar A=\E(A)$, and $Δ$ be the maximum expected degree of $G$ . Oliveira first proved that almost surely $\|A-\bar A\|=O(\sqrt{Δ\ln n})$ provided $Δ\geq C \ln n$ for some constant $C$ . Chung-Radcliffe improved the hidden constant in the error term using a new Chernoff-type inequality for random matrices. Here we prove that almost surely $\|A-\bar A\|\leq (2+o(1))\sqrtΔ$ with a slightly stronger condition $Δ\gg \ln^4 n$ . For the Laplacian $L$ of $G$ , Oliveira and Chung-Radcliffe proved similar results $\|L-\bar L|=O(\sqrt{\ln n}/\sqrtδ)$ provided the minimum expected degree $δ\gg \ln n$ ; we also improve their results by removing the $\sqrt{\ln n}$ multiplicative factor from the error term under some mild conditions. Our results naturally apply to the classic Erdős-Rényi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.

preprint2012arXiv

The Fractional Chromatic Number of Triangle-free Graphs with $Δ\leq 3$

Let $G$ be any triangle-free graph with maximum degree $Δ\leq 3$ . Staton proved that the independence number of $G$ is at least 5/14n. Heckman and Thomas conjectured that Staton's result can be strengthened into a bound on the fractional chromatic number of $G$ , namely $χ_f(G)\leq 14/5. Recently, Hatami and Zhu proved$ χ_f(G) \leq 3 -{3/64} $. In this paper, we prove$ χ_f(G) \leq 3- 3/43$.

preprint2011arXiv

A Fractional Analogue of Brooks' Theorem

Let $Δ(G)$ be the maximum degree of a graph $G$ . Brooks' theorem states that the only connected graphs with chromatic number $χ(G)=Δ(G)+1$ are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs $G$ such that the fractional chromatic number $χ_f(G)$ is at least $Δ(G)$ . These graphs are complete graphs, odd cycles, $C^2_8$ , $C_5\boxtimes K_2$ , and graphs whose clique number $ω(G)$ equals the maximum degree $Δ(G)$ . Among the two sporadic graphs, the graph $C^2_8$ is the square graph of cycle $C_8$ while the other graph $C_5\boxtimes K_2$ is the strong product of $C_5$ and $K_2$ . In fact, we prove a stronger result; if a connected graph $G$ with $Δ(G)\geq 4$ is not one of the graphs listed above, then we have $χ_f(G)\leq Δ(G)- 2/67$ .

preprint2011arXiv

High-ordered Random Walks and Generalized Laplacians on Hypergraphs

Despite of the extreme success of the spectral graph theory, there are relatively few papers applying spectral analysis to hypergraphs. Chung first introduced Laplacians for regular hypergraphs and showed some useful applications. Other researchers treated hypergraphs as weighted graphs and then studied the Laplacians of the corresponding weighted graphs. In this paper, we aim to unify these very different versions of Laplacians for hypergraphs. We introduce a set of Laplacians for hypergraphs through studying high-ordered random walks on hypergraphs. We prove the eigenvalues of these Laplacians can effectively control the mixing rate of high-ordered random walks, the generalized distances/diameters, and the edge expansions.

preprint2011arXiv

Loose Laplacian spectra of random hypergraphs

Let $H=(V,E)$ be an $r$ -uniform hypergraph with the vertex set $V$ and the edge set $E$ . For $1\leq s \leq r/2$ , we define a weighted graph $G^{(s)}$ on the vertex set ${V\choose s}$ as follows. Every pair of $s$ -sets $I$ and $J$ is associated with a weight $w(I,J)$ , which is the number of edges in $H$ passing through $I$ and $J$ if $I\cap J=\emptyset$ , and 0 if $I\cap J\not=\emptyset$ . The $s$ -th Laplacian $Ł^{(s)}$ of $H$ is defined to be the normalized Laplacian of $G^{(s)}$ . The eigenvalues of $\mathcal L^{(s)}$ are listed as $λ^{(s)}_0, λ^{(s)}_1,..., λ^{(s)}_{{n\choose s}-1}$ in non-decreasing order. Let $\barλ^{(s)}(H)=\max_{i\not=0}\{|1-λ^{(s)}_i|\}$ . The parameters $\barλ^{(s)}(H)$ and $λ^{(s)}_1(H)$ , which were introduced in our previous paper, have a number of connections to the mixing rate of high-ordered random walks, the generalized distances/diameters, and the edge expansions. For $0< p<1$ , let $H^r(n,p)$ be a random $r$ -uniform hypergraph over $[n]:={1,2,..., n}$ , where each $r$ -set of $[n]$ has probability $p$ to be an edge independently. For $1 \leq s \leq r/2$ , $p(1-p)\gg \frac{\log^4 n}{n^{r-s}}$ , and $1-p\gg \frac{\log n}{n^2}$ , we prove that almost surely $\barλ^{(s)}(H^r(n,p))\leq \frac{s}{n-s}+ (3+o(1))\sqrt{\frac{1-p}{{n-s\choose r-s}p}}.$ We also prove that the empirical distribution of the eigenvalues of $Ł^{(s)}$ for $H^r(n,p)$ follows the Semicircle Law if $p(1-p)\gg \frac{\log^{1/3} n}{n^{r-s}}$ and $1-p\gg \frac{\log n}{n^{2+2r-2s}}$ .

preprint2011arXiv

Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$

This paper is motivated by a recent result of Wolf \cite{wolf} on the minimum number of monochromatic 4-term arithmetic progressions(4-APs, for short) in $\Z_p$ , where $p$ is a prime number. Wolf proved that there is a 2-coloring of $\Z_p$ with 0.000386% fewer monochromatic 4-APs than random 2-colorings; the proof is probabilistic and non-constructive. In this paper, we present an explicit and simple construction of a 2-coloring with 9.3% fewer monochromatic 4-APs than random 2-colorings. This problem leads us to consider the minimum number of monochromatic 4-APs in $\Z_n$ for general $n$ . We obtain both lower bound and upper bound on the minimum number of monochromatic 4-APs in all 2-colorings of $\Z_n$ . Wolf proved that any 2-coloring of $\Z_p$ has at least $(1/16+o(1))p^2$ monochromatic 4-APs. We improve this lower bound into $(7/96+o(1))p^2$ . Our results on $\Z_n$ naturally apply to the similar problem on $[n]$ (i.e., $\{1,2,..., n\}$ ). In 2008, Parillo, Robertson, and Saracino \cite{prs} constructed a 2-coloring of $[n]$ with 14.6% fewer monochromatic 3-APs than random 2-colorings. In 2010, Butler, Costello, and Graham \cite{BCG} extended their methods and used an extensive computer search to construct a 2-coloring of $[n]$ with 17.35% fewer monochromatic 4-APs (and 26.8% fewer monochromatic 5-APs) than random 2-colorings. Our construction gives a 2-coloring of $[n]$ with 33.33% fewer monochromatic 4-APs (and 57.89% fewer monochromatic 5-APs) than random 2-colorings.

Xing Peng

Research overview

Is this your work?

16 publications

Large book--cycle Ramsey numbers

Extensions of Erdős-Gallai Theorem and Luo's Theorem with Applications

Extreme values of the stationary distribution of random walks on directed graphs

A path Turan problem for infinite graphs

Decomposition of random graphs into complete bipartite graphs

On the decomposition of random hypergraphs

The Ramsey number of generalized loose paths in uniform Hypergrpahs

On the chromatic number of the Erdős-Rényi orthogonal polarity graph

Bounds for generalized Sidon sets

Infinite Turán problems for bipartite graphs

Spectra of edge-independent random graphs

The Fractional Chromatic Number of Triangle-free Graphs with $Δ\leq 3$

A Fractional Analogue of Brooks' Theorem

High-ordered Random Walks and Generalized Laplacians on Hypergraphs

Loose Laplacian spectra of random hypergraphs

Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$

See the researcher in context

Building this map preview

Xing Peng

Research overview

Is this your work?

16 publications

Large book--cycle Ramsey numbers

Extensions of Erdős-Gallai Theorem and Luo's Theorem with Applications

Extreme values of the stationary distribution of random walks on directed graphs

A path Turan problem for infinite graphs

Decomposition of random graphs into complete bipartite graphs

On the decomposition of random hypergraphs

The Ramsey number of generalized loose paths in uniform Hypergrpahs

On the chromatic number of the Erdős-Rényi orthogonal polarity graph

Bounds for generalized Sidon sets

Infinite Turán problems for bipartite graphs

Spectra of edge-independent random graphs

The Fractional Chromatic Number of Triangle-free Graphs with Δ≤3Δ\leq 3Δ≤3

A Fractional Analogue of Brooks' Theorem

High-ordered Random Walks and Generalized Laplacians on Hypergraphs

Loose Laplacian spectra of random hypergraphs

Monochromatic 4-term arithmetic progressions in 2-colorings of Zn\mathbb Z_nZn​

See the researcher in context

Building this map preview

The Fractional Chromatic Number of Triangle-free Graphs with $Δ\leq 3$

Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$