Search

We construct a new Markov chain Monte Carlo method on finite states with optimal choices of acceptance-rejection ratio functions. We prove that the constructed continuous time Markov jumping process has a global in-time convergence rate in $L^1$ distance. The convergence rate is no less than one-half and is independent of the target distribution. For example, our method recovers the Metropolis-Hastings algorithm on a two-point state. And it forms a new algorithm for sampling general target distributions. Numerical examples are presented to demonstrate the effectiveness of the proposed algorithm.

The spread of a graph $G$ is the difference between the largest and smallest eigenvalues of the adjacency matrix of $G$. In this paper, we consider the family of graphs which contain no $K_{2,t}$-minor. We show that for any $t\geq 2$, there is an integer $\xi_t$ such that the maximum spread of an $n$-vertex $K_{2,t}$-minor-free graph is achieved by the graph obtained by joining a vertex to the disjoint union of $\lfloor \frac{2n+\xi_t}{3t}\rfloor$ copies of $K_t$ and $n-1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$ isolated vertices. The extremal graph is unique, except when $t\equiv 4 \mod 12$ and $\frac{2n+ \xi_t} {3t}$ is an integer, in which case the other extremal graph is the graph obtained by joining a vertex to the disjoint union of $\lfloor \frac{2n+\xi_t}{3t}\rfloor-1$ copies of $K_t$ and $n-1-t(\lfloor \frac{2n+\xi_t}{3t}\rfloor-1)$ isolated vertices. Furthermore, we give an explicit formula for $\xi_t$., Comment: Minor revisions. arXiv admin note: text overlap with arXiv:2209.13776

The spread of a graph $G$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $G$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $n$, the $n$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $\lceil (2n-1)/3\rceil$ vertices and $\lfloor(n-2)/3\rfloor$ isolated vertices. For planar graphs, we show that the extremal $n$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $\lceil(2n-2)/3\rceil$ vertices and $\lfloor(n-4)/3\rfloor$ isolated vertices.

In this paper, we generalize Lin-Lu-Yau's Ricci curvature to weighted graphs and give a simple limit-free definition. We prove two extremal results on the sum of Ricci curvatures for weighted graph. A weighted graph $G=(V,E,d)$ is an undirected graph $G=(V,E)$ associated with a distance function $d\colon E\to [0,\infty)$. By redefining the weights if possible, without loss of generality, we assume that the shortest weighted distance between $u$ and $v$ is exactly $d(u,v)$ for any edge $uv$. Now consider a random walk whose transitive probability from an vertex $u$ to its neighbor $v$ (a jump move along the edge $uv$) is proportional to $w_{uv}:=F(d(u,v))/d(u,v)$ for some given function $F(\bullet)$. We first generalize Lin-Lu-Yau's Ricci curvature definition to this weighted graph and give a simple limit-free representation of $\kappa(x, y)$ using a so called $\ast$-coupling functions. The total curvature $K(G)$ is defined to be the sum of Ricci curvatures over all edges of $G$. We proved the following theorems: if $F(\bullet)$ is a decreasing function, then $K(G)\geq 2|V| -2|E|$; if $F(\bullet)$ is an increasing function, then $K(G)\leq 2|V| -2|E|$. Both equalities hold if and only if $d$ is a constant function plus the girth is at least $6$. In particular, these imply a Gauss-Bonnet theorem for (unweighted) graphs with girth at least $6$, where the graph Ricci curvature is defined geometrically in terms of optimal transport.

We derive mean-field information Hessian matrices on finite graphs. The "information" refers to entropy functions on the probability simplex. And the "mean-field" means nonlinear weight functions of probabilities supported on graphs. These two concepts define a mean-field optimal transport type metric. In this metric space, we first derive Hessian matrices of energies on graphs, including linear, interaction energies, entropies. We name their smallest eigenvalues as mean-field Ricci curvature bounds on graphs. We next provide examples on two-point spaces and graph products. We last present several applications of the proposed matrices. E.g., we prove discrete Costa's entropy power inequalities on a two-point space.

Consider a matroid $M=(E,\mathcal{I})$ with its elements of the ground set $E$ colored. A rainbow basis is a maximum independent set in which each element receives a different color. The rank of a subset $S$ of $E$, denoted by $r_M(S)$, is the maximum size of an independent set in $S$. A flat $F$ is a maximal set in $M$ with a fixed rank. The anti-Ramsey number of $t$ pairwise disjoint rainbow bases in $M$, denoted by $ar(M,t)$, is defined as the maximum number of colors $m$ such that there exists an $m$ coloring of the ground set $E$ of $M$ which contains no $t$ pairwise disjoint rainbow bases. We determine $ar(M,t)$ for all matroids of rank at least 2: $ar(M,t)=|E|$ if there exists a flat $F_0$ with $|E|-|F_0, Comment: 19 pages

A graph is called Ricci-flat if its Ricci curvatures vanish on all edges, here the definition of Ricci curvature on graphs was given by Lin-Lu-Yau. The authors in arXiv:1301.0102 and arXiv:1802.02982 obtained a complete characterization for all Ricci-flat graphs with girth at least five. In this paper, we completely determined all Ricci-flat graphs with maximum degree at most 4., Comment: Notes of Ricci flat graphs with maximum degree at most 4.Proofs are in separated notes

An edge-colored graph $G$ is called \textit{rainbow} if every edge of $G$ receives a different color. Given any host graph $G$, the \textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees in $G$, denoted by $r(G,t)$, is defined as the maximum number of colors in an edge-coloring of $G$ containing no $t$ edge-disjoint rainbow spanning trees. For any vertex partition $P$, let $E(P,G)$ be the set of non-crossing edges in $G$ with respect to $P$. In this paper, we determine $r(G,t)$ for all host graphs $G$: $r(G,t)=|E(G)|$ if there exists a partition $P_0$ with $|E(G)|-|E(P_0,G), Comment: 11 pages

We consider the Tur\'an problems of $2$-edge-colored graphs. A $2$-edge-colored graph $H=(V, E_r, E_b)$ is a triple consisting of the vertex set $V$, the set of red edges $E_r$ and the set of blue edges $E_b$ with $E_r$ and $E_b$ do not have to be disjoint. The Tur\'an density $\pi(H)$ of $H$ is defined to be $\lim_{n\to\infty} \max_{G_n}h_n(G_n)$, where $G_n$ is chosen among all possible $2$-edge-colored graphs on $n$ vertices containing no $H$ as a sub-graph and $h_n(G_n)=(|E_r(G)|+|E_b(G)|)/{n\choose 2}$ is the formula to measure the edge density of $G_n$. We will determine the Tur\'an densities of all $2$-edge-colored bipartite graphs. We also give an important application of our study on the Tur\'an problems of $\{2, 3\}$-hypergraphs., Comment: 21 pages

We show that if a planar graph $G$ with minimum degree at least $3$ has positive Lin-Lu-Yau Ricci curvature on every edge, then $\Delta(G)\leq 17$, which then implies that $G$ is finite. This is an analogue of a result of DeVos and Mohar [{\em Trans. Amer. Math. Soc., 2007}] on the size of planar graphs with positive combinatorial curvature., Comment: 10 pages, 2 figures

We consider the Tur��n problems of $2$-edge-colored graphs. A $2$-edge-colored graph $H=(V, E_r, E_b)$ is a triple consisting of the vertex set $V$, the set of red edges $E_r$ and the set of blue edges $E_b$ with $E_r$ and $E_b$ do not have to be disjoint. The Tur��n density $��(H)$ of $H$ is defined to be $\lim_{n\to\infty} \max_{G_n}h_n(G_n)$, where $G_n$ is chosen among all possible $2$-edge-colored graphs on $n$ vertices containing no $H$ as a sub-graph and $h_n(G_n)=(|E_r(G)|+|E_b(G)|)/{n\choose 2}$ is the formula to measure the edge density of $G_n$. We will determine the Tur��n densities of all $2$-edge-colored bipartite graphs. We also give an important application of our study on the Tur��n problems of $\{2, 3\}$-hypergraphs., 21 pages

We study the existence of solutions of Ricci flow equations of Ollivier-Lin-Lu-Yau curvature defined on weighted graphs. Our work is motivated by\cite{NLLG} in which the discrete time Ricci flow algorithm has been applied successfully as a discrete geometric approach in detecting complex networks. Our main result is the existence and uniqueness theorem for solutions to a continuous time normalized Ricci flow. We also display possible solutions to the Ricci flow on path graph and prove the Ricci flow on finite star graph with at least three leaves converges to constant-weighted star., Comment: 17 pages

For a fixed set of positive integers $R$, we say $\mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a Berge-$G$, denoted by $BG$, if there exists a bijection $f: E(G) \to E(\mathcal{H})$ such that for every $e \in E(G)$, $e \subseteq f(e)$. In this paper, we define a variant of Tur\'an number in hypergraphs, namely the cover Tur\'an number, denoted as $\hat{ex}_R(n, G)$, as the maximum number of edges in the shadow graph of a Berge-$G$ free $R$-graph on $n$ vertices. We show a general upper bound on the cover Tur\'an number of graphs and determine the cover Tur\'an density of all graphs when the uniformity of the host hypergraph equals to $3$., Comment: 14 pages

For a fixed set of positive integers $R$, we say $\mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a Berge-$G$, denoted by $BG$, if there exists a bijection $f: E(G) \to E(\mathcal{H})$ such that for every $e \in E(G)$, $e \subseteq f(e)$. In this paper, we define a variant of Tur��n number in hypergraphs, namely the cover Tur��n number, denoted as $\hat{ex}_R(n, G)$, as the maximum number of edges in the shadow graph of a Berge-$G$ free $R$-graph on $n$ vertices. We show a general upper bound on the cover Tur��n number of graphs and determine the cover Tur��n density of all graphs when the uniformity of the host hypergraph equals to $3$., 14 pages

Frankl and F\"uredi conjectured in 1989 that the maximum Lagrangian, denoted by $\lambda_r(m)$, among all $r$-uniform hypergraphs of fixed size $m$ is achieved by the minimum hypergraph $C_{r,m}$ under the colexicographic order. We say $m$ in {\em principal domain} if there exists an integer $t$ such that ${t-1\choose r}\leq m\leq {t\choose r}-{t-2\choose r-2}$. If $m$ is in the principal domain, then Frankl-F\"uredi's conjecture has a very simple expression: $$\lambda_r(m)=\frac{1}{(t-1)^r}{t-1\choose r}.$$ Many previous results are focusing on $r=3$. For $r\geq 4$, Tyomkyn in 2017 proved that Frankl-F\"{u}redi's conjecture holds whenever ${t-1\choose r} \leq m \leq {t\choose r} -{t-2\choose r-2}- \delta_rt^{r-2}$ for a constant $\delta_r>0$. In this paper, we improve Tyomkyn's result by showing Frankl-F\"{u}redi's conjecture holds whenever ${t-1\choose r} \leq m \leq {t\choose r} -{t-2\choose r-2}- \delta_r't^{r-\frac{7}{3}}$ for a constant $\delta_r'>0$., Comment: 16 pages

An $(r,s)$-directed hypergraph is a directed hypergraph with $r$ vertices in tail and $s$ vertices in head of each arc. Let $G$ be an $(r,s)$-directed hypergraph. For any real numbers $p$, $q\geq 1$, we define the $(p,q)$-spectral radius $\lambda_{p,q}(G)$ as \[ \lambda_{p,q}(G):=\max_{||{\bf x}||_p=||{\bf y}||_q=1} \sum_{e\in E(G)}\Bigg(\prod_{u\in T(e)}x_u\Bigg)\Bigg(\prod_{v\in H(e)}y_v\Bigg), \] where ${\bf x}=(x_1, \ldots, x_m)^{{\rm T}}$, ${\bf y}=(y_1,\ldots, y_n)^{{\rm T}}$ are real vectors; and $T(e)$, $H(e)$ are the tail and head of arc $e$, respectively. We study some properties about $\lambda_{p,q}(G)$ including the bounds and the spectral relation between $G$ and its components. The $\alpha$-normal labeling method for uniform hypergraphs was introduced by Lu and Man in 2014. It is an effective method in studying the spectral radii of uniform hypergraphs. In this paper, we develop the $\alpha$-normal labeling method for calculating the $(p,q)$-spectral radii of $(r,s)$-directed hypergraphs. Finally, some applications of $\alpha$-normal labeling method are given., Comment: 39 pages

Let $G$ be an $r$-uniform hypergraph of order $n$. For each $p\geq 1$, the $p$-spectral radius $\lambda^{(p)}(G)$ is defined as \[ \lambda^{(p)}(G):=\max_{|x_1|^p+\cdots+|x_n|^p=1} r\sum_{\{i_1,\ldots,i_r\}\in E(G)}x_{i_1}\cdots x_{i_r}. \] The $p$-spectral radius was introduced by Keevash-Lenz-Mubayi, and subsequently studied by Nikiforov in 2014. The most extensively studied case is when $p=r$, and $\lambda^{(r)}(G)$ is called the spectral radius of $G$. The $\alpha$-normal labeling method, which was introduced by Lu and Man in 2014, is effective method for computing the spectral radii of uniform hypergraphs. It labels each corner of an edge by a positive number so that the sum of the corner labels at any vertex is $1$ while the product of all corner labels at any edge is $\alpha$. Since then, this method has been used by many researchers in studying $\lambda^{(r)}(G)$. In this paper, we extend Lu and Man's $\alpha$-normal labeling method to the $p$-spectral radii of uniform hypergraphs for $p\ne r$; and find some applications., Comment: 24 pages

In this paper, we consider the Tur\'an problems on $\{1,3\}$-hypergraphs. We prove that a $\{1, 3\}$-hypergraph is degenerate if and only if it's $H^{\{1, 3\}}_5$-colorable, where $H^{\{1, 3\}}_5$ is a hypergraph with vertex set $V=[5]$ and edge set $E=\{\{2\}, \{3\}, \{1, 2, 4\}, \{1, 3, 5\}, \{1, 4, 5\}\}.$ Using this result, we further prove that for any finite set $R$ of distinct positive integers, except the case $R=\{1, 2\}$, there always exist non-trivial degenerate $R$-graphs. We also compute the Tur\'an densities of some small $\{1,3\}$-hypergraphs., Comment: 18 pages

For $r\geq 2$ and $p\geq 1$, the $p$-spectral radius of an $r$-uniform hypergraph $H=(V,E)$ on $n$ vertices is defined to be $$\rho_p(H)=\max_{{\bf x}\in \mathbb{R}^n: \|{\bf x}\|_p=1}r \cdot \!\!\!\! \sum_{\{i_1,i_2,\ldots, i_r\}\in E(H)} x_{i_1}x_{i_2}\cdots x_{i_r},$$ where the maximum is taken over all ${\bf x\in \mathbb{R}^n}$ with the $p$-norm equals 1. In this paper, we proved for any integer $r\geq 2$, and any real $p\geq 1$, and any $r$-uniform hypergraph $H$ with $m={s\choose r}$ edges (for some real $s\geq r-1$), we have $$\lambda_p(H)\leq \frac{rm}{s^{r/p}}.$$ The equality holds if and only if $s$ is an integer and $H$ is the complete $r$-uniform hypergraph $K^r_s$ with some possible isolated vertices added. Thus, we completely settled a conjecture of Nikiforov. In particular, we settled all the principal cases of the Frankl-F\"{u}redi's Conjecture on the Lagrangians of $r$-uniform hypergraphs for all $r\geq 2$., Comment: 16 pages

In this paper, we consider the Tur��n problems on $\{1,3\}$-hypergraphs. We prove that a $\{1, 3\}$-hypergraph is degenerate if and only if it's $H^{\{1, 3\}}_5$-colorable, where $H^{\{1, 3\}}_5$ is a hypergraph with vertex set $V=[5]$ and edge set $E=\{\{2\}, \{3\}, \{1, 2, 4\}, \{1, 3, 5\}, \{1, 4, 5\}\}.$ Using this result, we further prove that for any finite set $R$ of distinct positive integers, except the case $R=\{1, 2\}$, there always exist non-trivial degenerate $R$-graphs. We also compute the Tur��n densities of some small $\{1,3\}$-hypergraphs., 18 pages

Frankl and F\"uredi conjectured in 1989 that the maximum Lagrangian of all $r$-uniform hypergraphs of fixed size $m$ is realized by the minimum hypergraph $C_{r,m}$ under the colexicographic order. In this paper, we prove a weaker version of the Frankl and F\"{u}redi's conjecture at $r=3$: there exists an absolute constant $c>0$ such that for any $3$-uniform hypergraph $H$ with $m$ edges, the Lagrangian of $H$ satisfies $\lambda(H)\leq \lambda(C_{3,m+cm^{2/9}})$. In particular, this result implies that the Frankl and F\"{u}redi's conjecture holds for $r=3$ and $m\in [{t-1\choose 3}, {t\choose 3}-(t-2)-ct^{\frac{2}{3}}]$. It improves a recent result of Tyomkyn., Comment: 9 page, 1 figure

In the cops and robber games played on a simple graph $G$, Aigner and Fromme's lemma states that one cop can guard a shortest path in the sense that the robber cannot enter this path without getting caught after finitely many steps. In this paper, we extend Aigner and Fromme's lemma to cover a larger family of graphs and give metric characterizations of these graphs. In particular, we show that a generalization of block graphs, namely vertebrate graphs, are 1-guardable. We use this result to give the cop number of some special class of multi-layer generalized Peterson graphs., Comment: fixing typos

Frankl and F��redi conjectured in 1989 that the maximum Lagrangian, denoted by $��_r(m)$, among all $r$-uniform hypergraphs of fixed size $m$ is achieved by the minimum hypergraph $C_{r,m}$ under the colexicographic order. We say $m$ in {\em principal domain} if there exists an integer $t$ such that ${t-1\choose r}\leq m\leq {t\choose r}-{t-2\choose r-2}$. If $m$ is in the principal domain, then Frankl-F��redi's conjecture has a very simple expression: $$��_r(m)=\frac{1}{(t-1)^r}{t-1\choose r}.$$ Many previous results are focusing on $r=3$. For $r\geq 4$, Tyomkyn in 2017 proved that Frankl-F��redi's conjecture holds whenever ${t-1\choose r} \leq m \leq {t\choose r} -{t-2\choose r-2}- ��_rt^{r-2}$ for a constant $��_r>0$. In this paper, we improve Tyomkyn's result by showing Frankl-F��redi's conjecture holds whenever ${t-1\choose r} \leq m \leq {t\choose r} -{t-2\choose r-2}- ��_r't^{r-\frac{7}{3}}$ for a constant $��_r'>0$., 16 pages

Let $G$ be an $r$-uniform hypergraph of order $n$. For each $p\geq 1$, the $p$-spectral radius $��^{(p)}(G)$ is defined as \[ ��^{(p)}(G):=\max_{|x_1|^p+\cdots+|x_n|^p=1} r\sum_{\{i_1,\ldots,i_r\}\in E(G)}x_{i_1}\cdots x_{i_r}. \] The $p$-spectral radius was introduced by Keevash-Lenz-Mubayi, and subsequently studied by Nikiforov in 2014. The most extensively studied case is when $p=r$, and $��^{(r)}(G)$ is called the spectral radius of $G$. The $��$-normal labeling method, which was introduced by Lu and Man in 2014, is effective method for computing the spectral radii of uniform hypergraphs. It labels each corner of an edge by a positive number so that the sum of the corner labels at any vertex is $1$ while the product of all corner labels at any edge is $��$. Since then, this method has been used by many researchers in studying $��^{(r)}(G)$. In this paper, we extend Lu and Man's $��$-normal labeling method to the $p$-spectral radii of uniform hypergraphs for $p\ne r$; and find some applications., 24 pages

The Kazhdan-Lusztig polynomial of a matroid was introduced by Elias, Proudfoot, and Wakefield [{\it Adv. Math. 2016}]. Let $U_{m,d}$ denote the uniform matroid of rank $d$ on a set of $m+d$ elements. Gedeon, Proudfoot, and Young [{\it J. Combin. Theory Ser. A, 2017}] pointed out that they can derive an explicit formula of the Kazhdan-Lusztig polynomials of $U_{m,d}$ using equivariant Kazhdan-Lusztig polynomials. In this paper we give two alternative explicit formulas, which allow us to prove the real-rootedness of the Kazhdan-Lusztig polynomials of $U_{m,d}$ for $2\leq m\leq 15$ and all $d$'s. The case $m=1$ was previously proved by Gedeon, Proudfoot, and Young [{\it S\'{e}m. Lothar. Combin. 2017}]. We further determine the $Z$-polynomials of all $U_{m,d}$'s and prove the real-rootedness of the $Z$-polynomials of $U_{m,d}$ for $2\leq m\leq 15$ and all $d$'s. Our formula also enables us to give an alternative proof of Gedeon, Proudfoot, and Young's formula for the Kazhdan-Lusztig polynomials of $U_{m,d}$'s without using the equivariant Kazhdan-Lusztig polynomials., Comment: 23 pages

For any positive integers $r$, $s$, $m$, $n$, an $(r,s)$-order $(n,m)$-dimensional rectangular tensor ${\cal A}=(a_{i_1\cdots i_r}^{j_1\cdots j_s}) \in ({\mathbb R}^n)^r\times ({\mathbb R}^m)^s$ is called partially symmetric if it is invariant under any permutation on the lower $r$ indexes and any permutation on the upper $s$ indexes. Such partially symmetric rectangular tensor arises naturally in studying directed hypergraphs. Ling and Qi [Front. Math. China, 2013] first studied the $(p,q)$-spectral radius (or singular values) and proved a Perron-Fronbenius theorem for such tensors when both $p,q \geq r+s$. We improved their results by extending to all $(p,q)$ satisfying $\frac{r}{p} +\frac{s}{q}\leq 1$. We also proved the Perron-Fronbenius theorem for general nonnegative $(r,s)$-order $(n,m)$-dimensional rectangular tensors when $\frac{r}{p}+\frac{s}{q}>1$. We essentially showed that this is best possible without additional conditions on $\cal A$. Finally, we applied these results to study the $(p,q)$-spectral radius of $(r,s)$-uniform directed hypergraphs., 1. One of the main results "Theorem 3.2" has already been proved under a more general setting by Antoine Gautier and Francesco Tudisco in the paper arXiv:1801.04215. 2. Example 2.1 contains an error; the strong eigenvalue-eigenvectors triple actually exists

Let $G$ be a graph. We say that a hypergraph $H$ is a Berge-$G$ if there is a bijection $\phi: E(G)\to E(H)$ such that $e\subseteq \phi(e)$ for all $e\in E(G)$. For any $r$-uniform hypergraph $H$ and a real number $p\geq 1$, the $p$-spectral radius $\lambda^{(p)}(H)$ of $H$ is defined as \[ \lambda^{(p)}(H):=\max_{{\bf x}\in\mathbb{R}^n,\,\|{\bf x}\|_p=1} r\sum_{\{i_1,i_2,\ldots,i_r\}\in E(H)} x_{i_1}x_{i_2}\cdots x_{i_r}. \] In this paper, we study the $p$-spectral radius of Berge-$G$ hypergraphs. We determine the $3$-uniform hypergraphs with maximum $p$-spectral radius for $p\geq 1$ among Berge-$G$ hypergraphs when $G$ is a path, a cycle or a star., Comment: 15 pages

The important nodes in complex networks are the extraordinary nodes which play more significant role than other nodes on the structure and function of the networks. In recent years, the reaserch on indentifying inflential nodes in complex networks has attracted much attention, because of its great theoretical significance as well as the wide range of applications. Aiming at different types of networks and motivated by different problems and applications, researchers have proposed groups of methods. This article systematically reviews more than 30 representative methods which are classified into four categories, and detailedly compares them from the aspects of computing ideas and application scenarios, and futher analyzes the strongness and weakness of each method. On this basis, this article summarizes the existing problems and outlines eight open issues as main challenges in the near future.

The burning number $b(G)$ of a graph $G$ was introduced by Bonato, Janssen, and Roshanbin [Lecture Notes in Computer Science 8882 (2014)] for measuring the speed of the spread of contagion in a graph. They proved for any connected graph $G$ of order $n$, $b(G)\leq 2\lceil \sqrt{n} \rceil-1$, and conjectured that $b(G)\leq \lceil \sqrt{n} \rceil$. In this paper, we proved $b(G)\leq \lceil\frac{-3+\sqrt{24n+33}}{4}\rceil$, which is roughly $\frac{\sqrt{6}}{2}\sqrt{n}$. We also settled the following conjecture of Bonato-Janssen-Roshanbin: $b(G)b(\bar G)\leq n+4$ provided both $G$ and $\bar G$ are connected.

We study the news system and explore news report mechanism based on the corpus of Sina news website. Instead of using complete content of news, we utilize short keywords to represent original news and mainly focus on the report time series of news. Empirical analysis shows that the distributions of time intervals follow power-law distribution with exponential cutoff on both single-class level and aggregate level. In addition, we analyze the vitality of keywords to explain why the distributions of different kinds of news show difference in the exponential cutoff tail. On the basis of these findings, we propose a hybrid mechanism queuing model to reveal the hidden principle of news reports. The simulation results can well fit the empirical data. The present study may shed some light on the mechanism of temporal patterns of news report and human selection behaviors.

Social networks constitute a new platform for information propagation, but its success is crucially dependent on the choice of spreaders who initiate the spreading of information. In this paper, we remove edges in a network at random and the network segments into isolated clusters. The most important nodes in each cluster then form a group of influential spreaders, such that news propagating from them would lead to an extensive coverage and minimal redundancy. The method well utilizes the similarities between the pre-percolated state and the coverage of information propagation in each social cluster to obtain a set of distributed and coordinated spreaders. Our tests on the Facebook networks show that this method outperforms conventional methods based on centrality. The suggested way of identifying influential spreaders thus sheds light on a new paradigm of information propagation on social networks., Comment: 17 pages, 4 figures and 1 table

Let $f(m,c)=\sum_{k=0}^{\infty} (km+1)^{k-1} c^k e^{-c(km+1)/m} / (m^kk!)$. For any positive integer $m$ and positive real $c$, the identity $f(m,c)=f(1,c)^{1/m}$ arises in the random graph theory. In this paper, we present two elementary proofs of this identity: a pure combinatorial proof and a power-serial proof. We also proved that this identity holds for any positive reals $m$ and $c$., Comment: 9 pages

The diffusion state distance (DSD) was introduced by Cao-Zhang-Park-Daniels-Crovella-Cowen-Hescott [{\em PLoS ONE, 2013}] to capture functional similarity in protein-protein interaction networks. They proved the convergence of DSD for non-bipartite graphs. In this paper, we extend the DSD to bipartite graphs using lazy-random walks and consider the general $L_q$-version of DSD. We discovered the connection between the DSD $L_q$-distance and Green's function, which was studied by Chung and Yau [{\em J. Combinatorial Theory (A), 2000}]. Based on that, we computed the DSD $L_q$-distance for Paths, Cycles, Hypercubes, as well as random graphs $G(n,p)$ and $G(w_1,..., w_n)$. We also examined the DSD distances of two biological networks., Accepted by the 11th Workshop on Algorithms and Models for the Web Graph (WAW2014)

Balogh and Bollob\'as [{\em Combinatorica 25, 2005}] prove that for any $k$ there is a constant $f(k)$ such that any set system with at least $f(k)$ sets reduces to a $k$-star, an $k$-costar or an $k$-chain. They proved $f(k)0$. This is a special case of the following result on the multi-coloured forbidden configurations at 2 colours. Let $r$ be given. Then there exists a constant $c_r$ so that a matrix with entries drawn from $\{0,1,...,r-1\}$ with at least $2^{c_rk^2}$ different columns will have a $k\times k$ submatrix that can have its rows and columns permuted so that in the resulting matrix will be either $I_k(a,b)$ or $T_k(a,b)$ (for some $a\ne b\in \{0,1,..., r-1\}$), where $I_k(a,b)$ is the $k\times k$ matrix with $a$'s on the diagonal and $b$'s else where, $T_k(a,b)$ the $k\times k$ matrix with $a$'s below the diagonal and $b$'s elsewhere. We also extend to considering the bound on the number of distinct columns, given that the number of rows is $m$, when avoiding a $t k\times k$ matrix obtained by taking any one of the $k \times k$ matrices above and repeating each column $t$ times. We use Ramsey Theory., Comment: 16 pages, add two applications

The hypergraph jump problem and the study of Lagrangians of uniform hypergraphs are two classical areas of study in the extremal graph theory. In this paper, we refine the concept of jumps to strong jumps and consider the analogous problems over non-uniform hypergraphs. Strong jumps have rich topological and algebraic structures. The non-strong-jump values are precisely the densities of the hereditary properties, which include the Tur\'an densities of families of hypergraphs as special cases. Our method uses a generalized Lagrangian for non-uniform hypergraphs. We also classify all strong jump values for $\{1,2\}$-hypergraphs., Comment: 19 pages

Zipf's law on word frequency is observed in English, French, Spanish, Italian, and so on, yet it does not hold for Chinese, Japanese or Korean characters. A model for writing process is proposed to explain the above difference, which takes into account the effects of finite vocabulary size. Experiments, simulations and analytical solution agree well with each other. The results show that the frequency distribution follows a power law with exponent being equal to 1, at which the corresponding Zipf's exponent diverges. Actually, the distribution obeys exponential form in the Zipf's plot. Deviating from the Heaps' law, the number of distinct words grows with the text length in three stages: It grows linearly in the beginning, then turns to a logarithmical form, and eventually saturates. This work refines previous understanding about Zipf's law and Heaps' law in language systems., 6 pages, 4 figures

The spectral radius $\rho(G)$ of a graph $G$ is the largest eigenvalue of its adjacency matrix. Woo and Neumaier discovered that a connected graph $G$ with $\rho(G)\leq 3/2{\sqrt{2}}$ is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Many open quipus and closed quipus have spectral radius greater than $3/2{\sqrt{2}}$. In this paper we proved the following results. For any open quipu $G$ on $n$ vertices ($n\geq 6$) with spectral radius less than $3/2{\sqrt{2}}$, its diameter $D(G)$ satisfies $D(G)\geq (2n-4)/3$. This bound is tight. For any closed quipu $G$ on $n$ vertices ($n\geq 13$) with spectral radius less than $3/2{\sqrt{2}}$, its diameter $D(G)$ satisfies $\frac{n}{3}< D(G)\leq \frac{2n-2}{3}$. The upper bound is tight while the lower bound is asymptotically tight. Let $G^{min}_{n,D}$ be a graph with minimal spectral radius among all connected graphs on $n$ vertices with diameter $D$. We applied the results and found $G^{min}_{n,D}$ for some range of $D$. For $n\geq 13$ and $D\in [\frac{n}{2}, \frac{2n-7}{3}]$, we proved that $G^{min}_{n,D}$ is the graph obtained by attaching two paths of length $D-\lfloor\frac{n}{2}\rfloor$ and $D-\lceil\frac{n}{2}\rceil$ to a pair of antipodal vertices of the even cycle $C_{2(n-D)}$. Thus we settled a conjecture of Cioab-van Dam-Koolen-Lee, who previously proved a special case $D=\frac{n+e}{2}$ for $e=1,2,3,4$., Comment: 18 pages

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., Comment: 23 pages, 4 figures

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., Comment: 19 pages, 3 figures

Let $G$ be any triangle-free graph with maximum degree $\Delta\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 $\chi_f(G)\leq 14/5. Recently, Hatami and Zhu proved $\chi_f(G) \leq 3 -{3/64}$. In this paper, we prove $\chi_f(G) \leq 3- 3/43$., Comment: Second revision: typos fixed, 24 pages, 37 figures

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$., Second revision: typos fixed, 24 pages, 37 figures

Our previous paper applied a lopsided version of the Lov\'asz Local Lemma that allows negative dependency graphs to the space of random injections from an $m$-element set to an $n$-element set. Equivalently, the same story can be told about the space of random matchings in $K_{n,m}$. Now we show how the cited version of the Lov\'asz Local Lemma applies to the space of random matchings in $K_{2n}$. We also prove tight upper bounds that asymptotically match the lower bound given by the Lov\'asz Local Lemma. As a consequence, we give new proofs to results on the enumeration of $d$-regular graphs. The tight upper bounds can be modified to the space of matchings in $K_{n,m}$, where they yield as application asymptotic formulas for permutation and Latin rectangle enumeration problems. The strength of the method is shown by a new result: enumeration of graphs by degree sequence or bipartite degree sequence and girth. As another application, we provide a new proof to the classical probabilistic result of Erd\H os that showed the existence of graphs with arbitrary large girth and chromatic number. If the degree sequence satisfies some mild conditions, almost all graphs with this degree sequence and prescribed girth have high chromatic number.

We examine a number of generalized and extended versions of concentration inequalities and martingale inequalities. These inequalities are effective for analyzing processes with quite general conditions as illustrated in an example for an infinite Polya process and web graphs.

This paper is motivated by a recent result of Wolf on the minimum number of monochromatic 4-term arithmetic progressions (4-APs, for short) in Zp, where p is a prime number. Wolf proved that there is a 2-coloring of Zp with 0.000386% fewer monochromatic 4-APs than random 2-colorings; the proof is probabilistic. 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 Zn for general n. We obtain both lower bound and upper bound on the minimum number of monochromatic 4-APs in Zn. Wolf proved that any 2-coloring of Zp has at least (1/16+o(1))p2 monochromatic 4-APs. We improve this lower bound to (7/96+o(1))p2.Our method for Zn naturally apply to the similar problem on [n]. In 2008, Parillo, Robertson, and Saracino constructed a 2-coloring of [n] with 14.6% fewer monochromatic 3-APs than random 2-colorings. In 2010, Butler, Costello, and Graham used a new method 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.