Tight Distance-Regular Graphs and the Q-Polynomial Property

 Let Γ denote a distance-regular graph with diameter d≥3, and assume Γ is tight (in the sense of Jurišić, Koolen and Terwilliger). Let θ denote the second largest or smallest eigenvalue of Γ, and let σ₀,σ₁,…,σ _d denote the associated cosine sequence. We obtain an inequality involving σ₀,σ₁,…,σ _d for each integer i (1≤i≤d−1), and we show equality for all i is closely related to Γ being Q-polynomial with respect to θ. We use this idea to investigate the Q-polynomial structures in tight distance-regular graphs. Received: January 30, 1998 Final version received: August 14, 1998     

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

Long and short paths in uniform random recursive dags

In a uniform random recursive k-directed acyclic graph, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If S _n is the shortest path distance from node n to the root, then we determine the constant σ such that S _n /log n→σ in probability as n→∞. We also show that max _1≤i≤n S _i /log n→σ in probability.     

On the Hopfield model at the critical temperature

We study the Hopfield model at temperature 1, when thenumber M(N) of patterns grows a bit slower than N. We reach a goodunderstanding of the model whenever M(N)≤N/(log N)¹¹. For example, we show that if M(N)→∞, for two typical configurations σ ¹, σ ², (∑ _{i ≤ N} σ¹ _i σ² _i )² is close to NM(N). Received: 15 December 1999 / Revised version: 8 December 2000 / Published online: 23 August 2001     

Weak Convergence of the Empirical Mean Excess Process with Application to Estimate the Negative Tail Index

Let Y _i , 1 ≤ i ≤ n be i.i.d. random variables with the generalized Pareto distribution W _γ,σ with γ < 0. We define the empirical mean excess process with respect to {Y _i , 1 ≤ i ≤ n} as in Eq. 2.1 (see below) and investigate its weak convergence. As an application, two new estimators of the negative tail index γ are constructed based on the linear regression to the empirical mean excess function and their consistency and asymptotic normality are obtained.      

PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS

§1　IntroductionGraphs considered in this paper are finite and simple.For a graph G,its vertex setandedge set are denoted by V(G) and E(G) ,respectively.If vertices u and v are connected inG,the distance between u and v,denoted by d G(u,v) ,is the length ofa shortest(u,v) -pathin G.The diameter of a connected graph G is the maximum distance between two verticesof G.For X V(G) ,the neighbor set NG(X) of X is defined byNG(X) ={ y∈V(G) \X:there is x∈X such thatxy∈E(G) } .NG({ x} )…     

Minimum ideal triangulations of hyperbolic 3-manifolds

Let σ(n) be the minimum number of ideal hyperbolic tetrahedra necessary to construct a finite volumen-cusped hyperbolic 3-manifold, orientable or not. Let σ_or(n) be the corresponding number when we restrict ourselves to orientable manifolds. The correct values of σ(n) and σ_or(n) and the corresponding manifolds are given forn=1,2,3,4 and 5. We then show that 2n−1≤σ(n)≤σ_or(n)≤4n−4 forn≥5 and that σ_or(n)≥2n for alln. Both authors were supported by NSF Grants DMS-8711495, DMS-8802266 and Williams College Research Funds.     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

Hamiltonian Cycles in Almost Claw-Free Graphs

 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G ₁, G ₂ and G ₃ such that E _G (G _i , G _j ) = {u _i , u _j , v _i v _j } for i≠j and i,j = 1, 2, 3 (where u _i ≠v _i ∈V(G _i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999     

Higher order Willmore hypersurfaces in Euclidean space

Let x ： Mn^n→ R^n＋1 be an n（≥2）-dimensional hypersurface immersed in Euclidean space Rn＋1. Let σi（0≤ i≤ n） be the ith mean curvature and Qn = ∑i=0^n（-1）^i＋1 （n^i）σ1^n-iσi. Recently, the author showed that Wn（x） = ∫M QndM is a conformal invariant under conformal group of R^n＋1 and called it the nth Willmore functional of x. An extremal hypersurface of conformal invariant functional Wn is called an nth order Willmore hypersurface. The purpose of this paper is to construct concrete examples of the 3rd order Willmore hypersurfaces in Ra which have good geometric behaviors. The ordinary differential equation characterizing the revolutionary 3rd Willmore hypersurfaces is established and some interesting explicit examples are found in this paper.     

On the frequency of Titchmarsh’s phenomenon for ζ(s)-VIII

For suitable functionsH = H(T) the maximum of|(ζ(σ + it)) ^z | taken overT≤t≤T + H is studied. For fixed σ(1/2≤σ≤l) and fixed complex constantsz “expected lower bounds” for the maximum are established.     

Precise asymptotics of error variance estimator in partially linear models

In this paper, we focus our attention on the precise asymptotics of error variance estimator in partially linear regression models, y _i = x _i ^τ β + g(t _i ) + ε _i , 1 ≤ i ≤ n, {ε _i , i = 1, ⋯ n} are i.i.d random errors with mean 0 and positive finite variance σ ². Following the ideas of Allan Gut and Aurel Spătaru^[7,8] and Zhang^[21], on precise asymptotics in the Baum-Katz and Davis laws of large numbers and precise rate in laws of the iterated logarithm, respectively, and subject to some regular conditions, we obtain the corresponding results in partially linear regression models.      

A remark on the unitary group of a tensor product of<Emphasis Type="Italic">n</Emphasis> finite-dimensional Hilbert spaces

LetH _i, 1 ≤ i ≤n be complex finite-dimensional Hilbert spaces of dimension d_i,1 ≤ i ≤n respectively withd _i ≥ 2 for everyi. By using the method of quantum circuits in the theory of quantum computing as outlined in Nielsen and Chuang [2] and using a key lemma of Jaikumar [1] we show that every unitary operator on the tensor productH =H ₁ ⊗H ₂ ⊗... ⊗H _n can be expressed as a composition of a finite number of unitary operators living on pair productsH _i ⊗H _j,1 ≤i,j ≤n. An estimate of the number of operators appearing in such a composition is obtained. Dedicated to Prof. A.K. Roy on his 62nd birthday.     

Univalent harmonic mappings of annuli and a conjecture of J. C. C. Nitsche

Letw=f(z) be a univalent harmonic mapping of the annulus {ρ≤|z|≤1} onto the annulus {σ≤|w|≤1}. It is shown thatσ≤1/(1+(ρ ²/2)(logρ)²).     

Bony attractors

A new possible geometry of an attractor of a dynamical system, a bony attractor, is described. A bony attractor is the union of two parts. The first part is the graph of a continuous function defined on a subset of ∑ ^k , the set of bi-infinite sequences of integers m in the range 0 ≤ m < k. The second part is the union of uncountably many intervals contained in the closure of the graph. An open set of skew products over the Bernoulli shift (σω) _i = ω _i+1 with fiber [0,1] is constructed such that each system in this set has a bony attractor.     

Chromatic uniqueness of certain complete tripartite graphs

Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k ²/4 + i + 1.     

Classification of regular embeddings of <Emphasis Type="Italic">n</Emphasis>-dimensional cubes

An orientably-regular map is a 2-cell embedding of a connected graph or multigraph into an orientable surface, such that the group of all orientation-preserving automorphisms of the embedding has a single orbit on the set of all arcs (incident vertex-edge pairs). Such embeddings of the n-dimensional cubes Q _n were classified for all odd n by Du, Kwak and Nedela in 2005, and in 2007, Jing Xu proved that for n=2m where m is odd, they are precisely the embeddings constructed by Kwon in 2004. Here, we give a classification of orientably-regular embeddings of Q _n for all n. In particular, we show that for all even n (=2m), these embeddings are in one-to-one correspondence with elements σ of order 1 or 2 in the symmetric group S _n such that σ fixes n, preserves the set of all pairs B _i ={i,i+m} for 1≤i≤m, and induces the same permutation on this set as the permutation B _i ↦ B _f(i) for some additive bijection f:ℤ _m →ℤ _m . We also give formulae for the numbers of embeddings that are reflexible and chiral, respectively, showing that the ratio of reflexible to chiral embeddings tends to zero for large even n.     

Zeros of linear recurrence sequences

Let be an exponential polynomial over a field of zero characteristic. Assume that for each pair i,j with i≠j, α _i /α _j is not a root of unity. Define . We introduce a partition of into subsets (1≤i≤m), which induces a decomposition of f into , so that, for 1≤i≤m, , while for , the number either is transcendental or else is algebraic with not too small a height. Then we show that for all but at most solutions x∈ℤ of f(x)= 0, we have