BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Xing Peng

Xing Peng contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COmath.NT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

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).

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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 \}|$.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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}}$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access