The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

Depth of functions of k-valued logic in finite bases

Realization of functions of the k-valued logic by circuits is considered over an arbitrary finite complete basis B. Asymptotic behavior of the Shannon function D _B (n) of the circuit depth over B is examined. The value D _B (n) is the minimal depth sufficient to realize every function of the k-valued logic of n variables by a circuit over B. It is shown that for each natural k ≥ 2 and for any finite complete basis B there exists a positive constant α _B such that D _B (n) ～ α _B n for n → ∞.     

Sudakov-type minoration for gaussian chaos processes

Consider a setA of symmetricn×n matricesa=(a _i,j) _i,j≤n . Consider an independent sequence (g _i) _i≤n of standard normal random variables, and letM=Esup_a∈A|Σ_i,j⪯na_i,jg_ig_j|. Denote byN ₂(A, α) (resp.N _t(A, α)) the smallest number of balls of radiusα for thel ₂ norm ofR ^{n 2} (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN ₂(A, α))^1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN _t≤K(δ)M. Work partially supported by an N.S.F. grant.     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

Zeros in Tables of Characters for the Groups <Emphasis Type="Italic">S</Emphasis><Subscript>n</Subscript> and <Emphasis Type="Italic">A</Emphasis><Subscript>n</Subscript>. II

Let P(n) be the set of all partitions of a natural number n. In the representation theory of symmetric groups, for every partition α ∈ P(n), the partition h(α) ∈ P(n) is defined so as to produce a certain set of zeros in the character table for S_n. Previously, the analog f(α) of h(α) was obtained pointing out an extra set of zeros in the table mentioned. Namely, h(α) is greatest (under the lexicographic ordering ≤) of the partitions β of n such that χ^α(g_β) ≠ 0, and f(α) is greatest of the partitions γ of n that are opposite in sign to h(α) and are such that χ^α(g_γ) ≠ 0, where χ^α is an irreducible character of S_n, indexed by α, and g_β is an element in the conjugacy class of S_n, indexed by β. For α ∈ P(n), under some natural restrictions, here, we construct new partitions h′(α) and f′(α) of n possessing the following properties. (A) Let α ∈ P(n) and n ⩾ 3. Then h′(α) is identical is sign to h(α), χ^α(g_h′(α)) ≠ 0, but χ^α(g_γ) = 0 for all γ ∈ P(n) such that the sign of γ coincides with one of h(α), and h′(α) < γ < h(α). (B) Let α ∈ P(n), α ≠ α′, and n ⩾ 4. Then f′(α) is identical in sign to f(α), χ^α(g_f′(α)) ≠ 0, but χ^α(g_γ) = 0 for all γ ∈ P(n) such that the sign of γ coincides with one of f(α), and f′(α) < γ < f(α). The results obtained are then applied to study pairs of semiproportional irreducible characters in A_n. Supported by RFBR grant No. 04-01-00463. __________ Translated from Algebra i Logika, Vol. 44, No. 6, pp. 643–663, November–December, 2005.     

On the total domination subdivision numbers in graphs

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sd_{γ t} (G) ≤ 2γ _t (G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sd_{γ t} (G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sd_{γ t} (G)=2γ _t (G)−1.     

THE SECOND EXPONENT SET OF PRIMITIVE DIGRAPHS

51.IntroductionandNotationsLetD=(V,E)beadigraphandL(D)denotethesetofcyclelengthsofD.ForuEVandintegeri21,letfo(u):={vEVIthereedestsadirectedwalkoflengthifromutov}.WedelveRo(u):={u}.Letu,vEV.IfN (v)=N (v)andN--(v)=N--(v),thenwecanvacopyofu.LotDbeaprimitivedigraphand7(D)denotetheexponentofD.In1950,H.WielandtI61foundthat7(D)5(n--1)' 1andshowedthatthereisapiquedigraphthatattainsthisbound.In1964,A.L.DulmageandN.S.Mendelsohn[2]ObservedthattherearegapsintheexponentsetEd={ry(D)IDEPD.}…     

Range of Brownian Motion with Drift

Let (B _δ (t)) _{t ≥ 0} be a Brownian motion starting at 0 with drift δ > 0. Define by induction S ₁=− inf _{t ≥ 0} B _δ (t), ρ₁ the last time such that B _δ (ρ₁)=−S ₁, S ₂=sup_{0≤ t ≤ρ 1} B _δ (t), ρ₂ the last time such that B _δ (ρ₂)=S ₂ and so on. Setting A _k =S _k +S _k+1; k ≥ 1, we compute the law of (A ₁,...,A _k ) and the distribution of (B _δ (t+ρ l) − B _δ (ρ _l ); 0 ≤ t ≤ ρ _l-1 − ρ _l )_{2 ≤ l ≤ k} for any k ≥ 2, conditionally on (A ₁,...,A _k ). We determine the law of the range R _δ (t) of (B _δ (s)) _{s≥ 0} at time t, and the first range time θ_δ (a) (i.e. θ_δ (a)=inf{t > 0; R _δ (t) > a}). We also investigate the asymptotic behaviour of θ _δ (a) (resp. R _δ (t)) as a → ∞ (resp. t → ∞).     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

On the Spectral Function of Some Higher Order Elliptic or Degenerate-elliptic Operators

^m σ/|α|=|β|=m D^α(a _αβD^β) is a higher order degenerate-elliptic operator on L²(R^N) and V ∈ L¹(R^N) we show in particular that s(λ) > 0 for all λ > 0 provided that ∫_RN V(x)dx≥ 0, V not equivalent to 0 and N ≤ 2m.     

Completely positive maps and*-isomorphism ofC *-algebras II

LetA, B be unitalC ^*-algebras,D _A ¹ the set of all completely positive maps ϕ fromA toM _n (C), with Tr ϕ(I)≤1(n≥3). If Ψ is an α-invariant affine homeomorphism betweenD _A ¹ andD _B ¹ with Ψ (0)=0, thenA is^*-isomorphic toB. Obtained results can be viewed as non-commutative Kadison-Shultz theorems. This work is supported by the National Natural Science Foundation of China.     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

On the general additive divisor problem

We obtain a new upper bound for the sum Σ _h≤H Δ _k (N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ _k (N, h) is the (expected) error term in the asymptotic formula for Σ _N<n≤2N d _k (n)d _k (n + h), and d _k (n) is the divisor function generated by ζ(s) ^k . When k = 3, the result improves, for H ≥ N ^1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3.     

The intersection of subgroups of finite <Emphasis Type="Italic">p</Emphasis>-groups

For a finite p-group G and a positive integer k let I _k (G) denote the intersection of all subgroups of G of order p ^k . This paper classifies the finite p-groups G with I_k(G) @ C_p^k-1{{I}_k(G)\cong C_{p^{k-1}}} for primes p > 2. We also show that for any k, α ≥ 0 with 2(α + 1) ≤ k ≤ n−α the groups G of order p ⁿ with I_k(G) @ C_p^k-a{{I}_k(G)\cong C_{p^{k-\alpha}}} are exactly the groups of exponent p ^n-α .     

Everywhere H?lder continuity of the spatial gradient of weak solutions to nonlinear parabolic systems

We consider weak solutions to the parabolic system ∂u ⁱ∂t−D _α A _i ^α (∇u)=B _i(∇u) in (i=1,...,) (Q=Ω×(0,T), R ⁿ a domain), where the functionsB _i may have a quadratic growth. Under the assumptionsn≤2 and ∇u ɛL _loc ^4+δ (Q; R ^nN ) (δ>0) we prove that ∇u is locally H?lder continuous inQ.     

On the generalization of the D. H. Lehmer problem

Let n ≥ 2 be a fixed positive integer, q ≥ 3 and c be two integers with （n, q） = （c, q） = 1. We denote by rn（51, 52, C; q） （δ 〈 δ1,δ2≤ 1） the number of all pairs of integers a, b satisfying ab ≡ c（mod q）, 1 〈 a ≤δ1q, 1 ≤ b≤δ2q, （a,q） = （b,q） = 1 and nt（a＋b）. The main purpose of this paper is to study the asymptotic properties of rn （δ1, δ2, c; q）, and give a sharp asymptotic formula for it.     

Wavelet expansions of fractal measures

Let μ be a measure on ℝⁿ that satisfies the estimate μ(B _r(x))≤cr ^α for allx ∈ ℝⁿ and allr ≤ 1 (B _r(x) denotes the ball of radius r centered atx. Let ϕ _j,k ^(ɛ) (x)=2 ^nj2ϕ^(ɛ)(2 ^j x-k) be a wavelet basis forj ∈ ℤ, κ ∈ ℤⁿ, and ∈ ∈E, a finite set, and letP _j (T)=Σ_ɛ,k <T,ϕ _j,k ^(ɛ) >ϕ _j,k ^(ɛ) denote the associated projection operators at levelj (T is a suitable measure or distribution). Iff ∈Ls ^p(dμ) for 1 ≤p ≤ ∞, we show thatP _j(f dμ) ∈ L^p(dx) and ||P _j (fdμ)||L _p(dx)≤c2 ^{j((n-α)/p′))}||f||L _p(dμ) for allj ≥ 0. We also obtain estimates for the limsup and liminf of ||P _j (fdμ)||L _p(dx) under more restrictive hypotheses. Communicated by Guido Weiss     

Total Domination in Partitioned Graphs

We present results on total domination in a partitioned graph G = (V, E). Let γ _t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ _t (G; V _i ) be the cardinality of a smallest subset of V such that every vertex of V _i has a neighbour in it and define the following

How many intervals cover a point in Dvoretzky covering?

Consider the Dvoretzky random covering with length sequence {α/n} _n≥1 (α>0). We are interested in the setF _β of points on the circle which are covered by a numberβ logn of the firstn randomly placed intervals. It is proved among others that for a certain interval ofβ>0, the Hausdorff dimension ofF _β is equal to 1−[βlog(β/α)−(β−α)]. This implies that points on the circle are differently covered. The research was partially supported by the Zheng Ge Ru Foundation and the RGC grant of Hong Kong.