On the chromatic number of random geometric graphs

Given independent random points X ₁,...,X _n ∈ℝ ^d with common probability distribution ν, and a positive distance r=r(n)>0, we construct a random geometric graph G _n with vertex set {1,..., n} where distinct i and j are adjacent when ‖X _i −X _j ‖≤r. Here ‖·‖ may be any norm on ℝ ^d , and ν may be any probability distribution on ℝ ^d with a bounded density function. We consider the chromatic number χ(G _n ) of G _n and its relation to the clique number ω(G _n ) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d} and the range when $r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider the ‘phase change’ range when $r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d}$r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d} with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants c(t) such that $\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t)$\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t) almost surely. Further, we find a “sharp threshold” (except for less interesting choices of the norm when the unit ball tiles d-space): there is a constant t ₀>0 such that if t≤t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to 1 almost surely, but if t>t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to a limit >1 almost surely.     

Joint asymptotic distribution of exceedances point process and partial sum of stationary Gaussian sequence

Let {X _i } _i=1^∞ be a standardized stationary Gaussian sequence with covariance function r(n) = EX ₁ X _n+1, S _n = Σ _i=1 ⁿ X _i , and $\bar X_n = \tfrac{{S_n }} {n} $\bar X_n = \tfrac{{S_n }} {n} . And let N _n be the point process formed by the exceedances of random level $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n by X ₁,X ₂,…, X _n . Under some mild conditions, N _n and S _n are asymptotically independent, and N _n converges weakly to a Poisson process on (0,1].     

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

On the trigonometric polynomials of Fejér and Young

The trigonometric polynomials of Fejér and Young are defined by $S_n (x) = \sum\nolimits_{k = 1}^n {\tfrac{{\sin (kx)}} {k}}$S_n (x) = \sum\nolimits_{k = 1}^n {\tfrac{{\sin (kx)}} {k}} and $C_n (x) = 1 + \sum\nolimits_{k = 1}^n {\tfrac{{\cos (kx)}} {k}}$C_n (x) = 1 + \sum\nolimits_{k = 1}^n {\tfrac{{\cos (kx)}} {k}}, respectively. We prove that the inequality $\left( {{1 \mathord{\left/ {\vphantom {1 9}} \right. \kern-\nulldelimiterspace} 9}} \right)\sqrt {15} \leqslant {{C_n \left( x \right)} \mathord{\left/ {\vphantom {{C_n \left( x \right)} {S_n \left( x \right)}}} \right. \kern-\nulldelimiterspace} {S_n \left( x \right)}}$\left( {{1 \mathord{\left/ {\vphantom {1 9}} \right. \kern-\nulldelimiterspace} 9}} \right)\sqrt {15} \leqslant {{C_n \left( x \right)} \mathord{\left/ {\vphantom {{C_n \left( x \right)} {S_n \left( x \right)}}} \right. \kern-\nulldelimiterspace} {S_n \left( x \right)}} holds for all n ≥ 2 and x ∈ (0, π). The lower bound is sharp.     

Proof of a conjecture of V. Nikiforov

Using analytical tools, we prove that for any simple graph G on n vertices and its complement [`(G)]\bar G the inequality $\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1$\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1 holds, where μ(G) and m( [`(G)] )\mu \left( {\bar G} \right) denote the greatest eigenvalue of adjacency matrix of the graphs G and [`(G)]\bar G respectively.     

A condition for asymptotic finite-dimensionality of an operator semigroup

Let X be a Banach space and let T: X → X be a power bounded linear operator. Put X ₀ = {x ∈ X ∣ T ⁿ x → 0}. Assume given a compact set K ⊂ X such that lim inf _n→∞ ρ{T ⁿ x, K} ≤ η < 1 for every x ∈ X, ∥x∥ ≤ 1. If $\eta < \tfrac{1} {2} $\eta < \tfrac{1} {2} , then codim X ₀ < ∞. This is true in X reflexive for $\eta \in [\tfrac{1} {2},1) $\eta \in [\tfrac{1} {2},1) , but fails in the general case.     

On the Fon-Der-Flaass interpretation of extremal examples for Turán’s (3, 4)-problem

Fon-Der-Flaass (1988) presented a general construction that converts an arbitrary [(C)\vec]₄\vec C_4 -free oriented graph Γ into a Turán (3, 4)-graph. He observed that all Turán-Brown-Kostochka examples result from his construction, and proved the lower bound $\tfrac{4} {9} $\tfrac{4} {9} (1 − o(1)) on the edge density of any Turán (3, 4)-graph obtainable in this way. In this paper we establish the optimal bound $\tfrac{3} {7} $\tfrac{3} {7} (1 − o(1)) on the edge density of any Turán (3, 4)-graph resulting from the Fon-Der-Flaass construction under any of the following assumptions on the undirected graph G underlying the oriented graph Γ: (i) G is complete multipartite; (ii) the edge density of G is not less than $\tfrac{2} {3} - \varepsilon $\tfrac{2} {3} - \varepsilon for some absolute constant ε > 0. We are also able to improve Fon-Der-Flaass’s bound to $\tfrac{7} {{16}} $\tfrac{7} {{16}} (1 − o(1)) without any extra assumptions on Γ.     

Stability of symmetric closed characteristics on symmetric compact convex hypersurfaces in ℝ<Superscript>2<Emphasis Type="Italic">n</Emphasis></Superscript> under a pinching condition

In this paper, let Σ R2n be a symmetric compact convex hypersurface which is ( r, R )- pinched with R/r (5/3)1/2 . Then Σ carries at least two elliptic symmetric closed characteristics; moreover, Σ carries at least E [ n-1/2 ] + E [ n-1/3 ] non-hyperbolic symmetric closed characteristics.     

Greedy Algorithm Computing Minkowski Reduced Lattice Bases with Quadratic Bit Complexity of Input Vectors

The authors present an algorithm which is a modification of the Nguyen-Stehle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) , where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O(log² A) algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n! · 3 ⁿ (log A) ^O(1) algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n! · (log A) ^O(1) by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.     

Uniform boundedness of (<Emphasis Type="Italic">C</Emphasis>, 1) means of Jacobi expansions in weighted sup norms. II (Some necessary estimations)

The paper is concerned with bounds for integrals of the type

On rigidity of Clifford torus in a unit sphere

We extend the scalar curvature pinching theorems due to Peng-Terng, Wei-Xu and Suh-Yang. Let M be an n-dimensional compact minimal hypersurface in S n+1 satisfying Sf 4 f_3~2 ≤ 1/n S~3 , where S is the squared norm of the second fundamental form of M, and f_k =sum λ_i~k from i and λ_i (1 ≤ i ≤ n) are the principal curvatures of M. We prove that there exists a positive constant δ(n)(≥ n/2) depending only on n such that if n ≤ S ≤ n + δ(n), then S ≡ n, i.e., M is one of the Clifford torus S~k ((k/n)~1/2 ) ×S~...     

On <Emphasis Type="Italic">T</Emphasis> points of algebroid functions

In this paper, we firstly give a new definition, namely, the T point of algebroid functions. Then by using Ahlfors’ theory of covering surfaces, we prove the existence of these points for any ν-valued algebroid functions in the unit disk satisfying $\mathop {\lim \sup }\limits_{r \to 1^ - } \frac{{T(r,w)}} {{\log \tfrac{1} {{1 - r}}}} = + \infty $\mathop {\lim \sup }\limits_{r \to 1^ - } \frac{{T(r,w)}} {{\log \tfrac{1} {{1 - r}}}} = + \infty . This extends the recent results of Xuan, Wu and Sun.     

Some Inequalities for Tree Martingales

In this paper we study tree martingales and proved that if 1≤α,β〈∞,1≤p〈∞ then for every predictable tree martingale f=（ft,t∞T）and E[σ^（P）（f）]〈∞,E[S^（P）（f）]〈∞,it holds that ‖（St^（p）（f）,t∈T）‖M^α∞≤Cαβ‖f‖p^αβ,‖（σt^（p）（f）,t∈T）‖M^α,β‖f‖P^αβ,where Cαβ depends only on α and β.     

On super vertex-graceful unicyclic graphs

A graph G with p vertices and q edges, vertex set V(G) and edge set E(G), is said to be super vertex-graceful (in short SVG), if there exists a function pair (f, f ⁺) where f is a bijection from V(G) onto P, f ⁺ is a bijection from E(G) onto Q, f ⁺((u, v)) = f(u) + f(v) for any (u, v) ∈ E(G),

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

On the Value Distribution of Hurwitz Zeta-Functions at the Nontrivial Zeros of the Riemann Zeta-Function

We consider the value distribution of Hurwitz zeta-functions at the nontrivial zeros ϱ= β + iγ of the Riemann zeta-function ζ (s):= ζ (s, 1). Using the method of Conrey, Ghosh and Gonek we prove for fixed 0< α< 1 andH ≤T that

On the Boundary Behaviour,Including Second Order Effects,of Solutions to Singular Elliptic Problems

For γ≥1 we consider the solution u=u（x） of the Dirichlet boundary value problem Δu ＋ u^-γ=0 in Ω, u=0 on δΩ. For γ= 1 we find the estimate u（x）=p（δ（x））[1＋A（x）（log 1/δ（x）^-6], where p（r） ≈ r r√2 log（1/r） near r = 0,δ（x） denotes the distance from x to δΩ, 0 〈ε 〈 1/2, and A（x） is a bounded function. For 1 〈 γ 〈 3 we find u（x）=（γ＋1/√2（γ-1）δ（x））^2/γ＋[1＋A（x）（δ（x））2γ-1/γ＋1] For γ3= we prove that u（x）=（2δ（x））^1/2[1＋A（x）δ（x）log 1/δ（x）]     

Domination numbers of undirected toroidal mesh

The (d, m)-domination number γd,m is a new measure to characterize the reliability of resources-sharing in fault tolerant networks, in some sense, which can more accurately characterize the reliability of networks than the m-diameter does. In this paper, we study the (d, 4)-domination numbers of undirected toroidal mesh Cd1 × Cd2 for some special values of d, obtain that γd,4 (Cd1 × C3) = 2 if and only if d4(G) e1 ≤ d d4(G) for d1 ≥ 5, γd,4 (Cd1 × C4) = 2 if d4(G) (2e1-[d1+e1]/2) ≤ d d4(G) for d1 ≥ 24, and γd,4 (Cd1 × Cd2 ) = 2 if d4(G) ( e1-2) ≤ d d4(G) for d1 = d2 ≥ 14.     

Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V ₁ and V ₀ so that in G[V ₁] every vertex has degree at most 1, while G[V ₀] is edgeless. We prove that every graph with maximum average degree at most $\tfrac{{12}} {5} $\tfrac{{12}} {5} is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to $\tfrac{{12}} {5} $\tfrac{{12}} {5} which are not (1, 0)-colorable.     

Limit theorems for the ratio of the Kaplan-Meier estimator or the Altshuler estimator to the true survival function

LetX ₁,X ₂, ...,X _n be a sequence of nonnegative independent random variables with a common continuous distribution functionF. LetY ₁,Y ₂, ...,Y _n be another sequence of nonnegative independent random variables with a common continuous distribution functionG, also independent of {X _i }. We can only observeZ _i =min(X _i ,Y _i ), and . LetH=1−(1−F)(1−G) be the distribution function ofZ. In this paper, the limit theorems for the ratio of the Kaplan-Meier estimator or the Altshuler estimator to the true survival functionS(t) are given. It is shown that (1)P(δ_(n)=1 i.o.)=0 ifF(τ _H ) < 1 andP(δ _n =0 i.o. )=0 ifG(τH) > 1 where δ_(n) is the corresponding indicator function of and have the same order a.s., where {T _n } is a sequence of constants such that 1−H(T _n )=n ^−α(logn)^β(log logn)^γ.