Small time convergence of subordinators with regularly or slowly varying canonical measure

We consider subordinators $X_{\alpha }={\left(X_{\alpha }\left(t\right)\right)}_{t\ge 0}$ in the domain of attraction at 0 of a stable subordinator ${\left(S_{\alpha }\left(t\right)\right)}_{t\ge 0}$ (where $\alpha \in (0,1)$); thus, with the property that ${\overline{\Pi }}_{\alpha }$, the tail function of the canonical measure of $X_{\alpha }$, is regularly varying of index $?\alpha \in (?1,0)$ as $x\downarrow 0$. We also analyse the boundary case, $\alpha =0$, when ${\overline{\Pi }}_{\alpha }$ is slowly varying at 0. When $\alpha \in (0,1)$, we show that ${\left(t{\overline{\Pi }}_{\alpha }\left(X_{\alpha }\left(t\right)\right)\right)}^{?1}$ converges in distribution, as $t\downarrow 0$, to the random variable ${\left(S_{\alpha }\left(1\right)\right)}^{\alpha }$. This latter random variable, as a function of $\alpha$, converges in distribution as $\alpha \downarrow 0$ to the inverse of an exponential random variable. We prove these convergences, also generalised to functional versions (convergence in $\mathbb{D}[0,1]$), and to trimmed versions, whereby a fixed number of its largest jumps up to a specified time are subtracted from the process. The $\alpha =0$ case produces convergence to an extremal process constructed from ordered jumps of a Cauchy subordinator. Our results generalise random walk and stable process results of Darling, Cressie, Kasahara, Kotani and Watanabe.     

On the centre of mass of a random walk

For a random walk $S_n$ on ${\mathbb{R}}^d$ we study the asymptotic behaviour of the associated centre of mass process $G_n=n^{?1}{\sum }_{i=1}^n{S}_i$. For lattice distributions we give conditions for a local limit theorem to hold. We prove that if the increments of the walk have zero mean and finite second moment, $G_n$ is recurrent if $d=1$ and transient if $d\ge 2$. In the transient case we show that $G_n$ has a diffusive rate of escape. These results extend work of Grill, who considered simple symmetric random walk. We also give a class of random walks with symmetric heavy-tailed increments for which $G_n$ is transient in $d=1$.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

Erdős–Gallai stability theorem for linear forests

The Erd?s–Gallai Theorem states that every graph of average degree more than $l?2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erd?s–Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=\left({?}_{i=1}^k{P}_{2a_i}\right)?\left({?}_{i=1}^l{P}_{2b_i+1}\right)$ be $k+l$ disjoint paths of order $2a_1,\dots ,2a_k,2b_1+1,\dots ,2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\ge 2$. If the minimum degree $\delta \left(G\right)\ge {\sum }_{i=1}^k{a}_i+{\sum }_{i=1}^l{b}_i?1$, then $F?G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.     

Ergodic aspects of some Ornstein–Uhlenbeck type processes related to Lévy processes

This work concerns the Ornstein–Uhlenbeck type process associated to a positive self-similar Markov process ${\left(X\left(t\right)\right)}_{t\ge 0}$ which drifts to $\infty$, namely $U\left(t\right)?{\mathrm{e}}^{?t}X({\mathrm{e}}^t?1)$. We point out that $U$ is always a (topologically) recurrent ergodic Markov process. We identify its invariant measure in terms of the law of the exponential functional $\stackrel{?}{I}?{\int }_0^{\infty }exp\left({\stackrel{?}{\xi }}_s\right)\mathrm{d}s$, where $\stackrel{?}{\xi }$ is the dual of the real-valued Lévy process $\xi$ related to $X$ by the Lamperti transformation. This invariant measure is infinite (i.e. $U$ is null-recurrent) if and only if ${\xi }_1?L^1\left(\mathbb{P}\right)$. In that case, we determine the family of Lévy processes $\xi$ for which $U$ fulfills the conclusions of the Darling–Kac theorem. Our approach relies crucially on a remarkable connection due to Patie (Patie, 2008) with another generalized Ornstein–Uhlenbeck process that can be associated to the Lévy process $\xi$, and properties of time-substitutions based on additive functionals.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

Ramsey number of multiple copies of stars

Let G and H be simple graphs. The Ramsey number $r(G,H)$ is the minimum integer N such that any red-blue-coloring of edges of $K_N$ contains either a red copy of G or a blue copy of H. Let $m{K}_{1,t}$ denote m vertex-disjoint copies of $K_{1,t}$. A lower bound is that $r(m{K}_{1,t},n{K}_{1,s})\ge m(t+1)+n?1$. Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t=s=3$, $m\ge 2$ and $m\ge n$. In this paper, we show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t\ge s=3,m\ge 2$ and $m\ge n$. We also show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $s\ge 4,t>\frac{s(s?1)}{2}$ and $m>n$.