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.}…     

Classi localmente filtrali

Riassunto Si dà la definizione di classe ?localmente filtrale?. Si diceche K è una classe localmente filtrale se per ogni n∈ω, per ogni A ₀,...,A _n−1, εK e per ogni famiglia di sotto-insiemi V_i di A_i (i∈n) con V_i finiti, la classe {B ₀,...,B _n−1 delle algebre generate da V₀, ..., V_n−1 è costituita da algebre finite ed è filtrale. Si dimostra che seK è localmente filtrale alloraV _L(K)=IR _L DS(K) e si dà un teorema di caratterizzazione per queste classi.

---

Summary We define a ?classe localmente filtrale? as follows: LetK be a class of similar algebras;K is a ?classe localmente filtrale? if for andn ∈ ω and for anyA ₀,...,A _n−1 ink and for any family of finite subsetsV _i ofA _i(i∈n), the class {B ₀,...,B _n−1 of algebras generated byV _o, ...,V _n−1 consists of finite algebras and is ?filtrale?. We show that ifK is ?localmente filtrale? thenV _L (K)=IR _L DS(K) and we give a characterization theorem for these classes.

---

---

Lavoro eseguito nell'ambito dei gruppi di ricerca matematici del C.N.R. per l'anno 1970–71.     

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.     

The nearness problems for symmetric centrosymmetric with a special submatrix constraint

We say that X=[x_ij]_i,j=1ⁿX=[x_{ij}]_{i,j=1}^n is symmetric centrosymmetric if x _ij  = x _ji and x _{n − j + 1,n − i + 1}, 1 ≤ i,j ≤ n. In this paper we present an efficient algorithm for minimizing ||AXA ^T  − B|| where ||·|| is the Frobenius norm, A ∈ ℝ ^m×n , B ∈ ℝ ^m×m and X ∈ ℝ ^n×n is symmetric centrosymmetric with a specified central submatrix [x _ij ] _{p ≤ i,j ≤ n − p} . Our algorithm produces a suitable X such that AXA ^T  = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

A local variational relation and applications

In [BGH] the authors show that for a given topological dynamical system (X,T) and an open coveru there is an invariant measure μ such that infh _μ(T,ℙ)≥h _top(T,U) where infimum is taken over all partitions finer thanu. We prove in this paper that if μ is an invariant measure andh _μ(T,ℙ) > 0 for each ℙ finer thanu, then infh _μ(T,ℙ > 0 andh _top(T,U) > 0. The results are applied to study the topological analogue of the Kolmogorov system in ergodic theory, namely uniform positive entropy (u.p.e.) of ordern (n≥2) or u.p.e. of all orders. We show that for eachn≥2 the set of all topological entropyn-tuples is the union of the set of entropyn-tuples for an invariant measure over all invariant measures. Characterizations of positive entropy, u.p.e. of ordern and u.p.e. of all orders are obtained. We could answer several open questions concerning the nature of u.p.e. and c.p.e.. Particularly, we show that u.p.e. of ordern does not imply u.p.e. of ordern+1 for eachn≥2. Applying the methods and results obtained in the paper, we show that u.p.e. (of order 2) system is weakly disjoint from all transitive systems, and the product of u.p.e. of ordern (resp. of all orders) systems is again u.p.e. of ordern (resp. of all orders). Project supported by one hundred talents plan and 973 plan.     

Constant-Sign Solutions for Systems of Fredholm and Volterra Integral Equations: The Singular Case

We consider the system of Fredholm integral equations

Decompositions of the Hardy space Hz^1（Ω）

We give a decomposition of the Hardy space Hz^1（Ω） into ＂div-curl＂ quantities for Lipschitz domains in R^n. We also prove a decomposition of Hz^1（Ω） into Jacobians det Du, u ∈ W0^1,2 （Ω,R^2） for Ω in R^2. This partially answers a well-known open problem.     

Topological ergodic decompositions and applications to products of powers of a minimal transformation

For a minimal distal flow (X, T) and a positive integern, let be the largest distal factor of ordern. The existence of a denseG _δ subset ω ofX is shown, such that forx ∈ ω the orbit closure of (x,x,...,x) ∈ X ⁿ⁺¹ under τ =T ×T ² ... ×T ⁿ⁺¹ is π-saturated. In fact, an analogous statement for a general minimal flow is proved in terms of its PI-tower. On the way we get some topological “ergodic” decomposition theorems.     

Fixed point theorems for non-Lipschitzian mappings of asymptotically nonexpansive type

LetX be a Banach space,K a nonempty, bounded, closed and convex subset ofX, and supposeT:K→K satisfies: for eachx∈K, lim sup _i→∞{sup _y∈K ‖t ⁱx−Tⁱy∼−‖x−y‖}≦0. IfT ^N is continuous for some positive integerN, and if either (a)X is uniformly convex, or (b)K is compact, thenT has a fixed point inK. The former generalizes a theorem of Goebel and Kirk for asymptotically nonexpansive mappings. These are mappingsT:K→K satisfying, fori sufficiently large, ‖Tⁱx−Tⁱy‖≦k _i‖x−y∼,x,y∈K, wherek _i→1 asi→∞. The precise assumption in (a) is somewhat weaker than uniform convexity, requiring only that Goebel’s characteristic of convexity, ɛ₀ (X), be less than one. Research supported by National Science Foundation Grant GP 18045.     

Minimum Cost Homomorphism Dichotomy for Oriented Cycles

For digraphs D and H, a mapping f : V(D) → V(H) is a homomorphism of D to H if uv ∈ A(D) implies f(u) f(v) ∈ A(H). If, moreover, each vertex u ∈ V(D) is associated with costs c _i (u), i ∈ V(H), then the cost of the homomorphism f is ∑ _{u ∈V(D)} c _f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem for H (abbreviated MinHOM(H)). The problem is to decide, for an input graph D with costs c _i (u), u ∈ V(D), i ∈ V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost. We obtain a dichotomy classification for the time complexity of MinHOM(H) when H is an oriented cycle. We conjecture a dichotomy classification for all digraphs with possible loops.     

Existence of singular solutions of a degenerate equation in R 2

Let a₁,a₂, . . . ,a_m ∈ ℝ², 2≤f ∈ C([0,∞)), g_i ∈ C([0,∞)) be such that 0≤g_i(t)≤2 on [0,∞) ∀i=1, . . . ,m. For any p>1, we prove the existence and uniqueness of solutions of the equation u_t=Δ(logu), u>0, in satisfying and logu(x,t)/log|x|→−f(t) as |x|→∞, logu(x,t)/log|x−a_i|→−g_i(t) as |x−a_i|→0, uniformly on every compact subset of (0,T) for any i=1, . . . ,m under a mild assumption on u₀ where We also obtain similar existence and uniqueness of solutions of the above equation in bounded smooth convex domains of ℝ² with prescribed singularities at a finite number of points in the domain.     

On a Delay Reaction-Diffusion Difference Equation of Neutral Type

In this paper, we first consider a delay difference equation of neutral type of the form: Δ(y _n + py _n−k + q _n y _n−l = 0 for n∈ℤ⁺(0) (1*) and give a different condition from that of Yu and Wang (Funkcial Ekvac, 1994, 37(2): 241–248) to guarantee that every non-oscillatory solution of (1*) with p = 1 tends to zero as n→∞. Moreover, we consider a delay reaction-diffusion difference equation of neutral type of the form: Δ₁(u _n,m + pu _n−k,m ) + q _n,m u _n−l,m = a ²Δ² ₂ u _{n +1, m−1} for (n,m) ∈ℤ⁺ (0) ×Ω, (2*) study various cases of p in the neutral term and obtain that if p≥−1 then every non-oscillatory solution of (2*) tends uniformly in m∈Ω to zero as n→∞; if p = −1 then every solution of (2*) oscillates and if p < −1 then every non-oscillatory solution of (2*) goes uniformly in m∈Ω to infinity or minus infinity as n→∞ under some hypotheses. Received July 14, 1999, Revised August 10, 2000, Accepted September 30, 2000     

Product of Uniform Distribution and Stirling Numbers of the First Kind

Let Vk=u1u2……uk, ui＇s be i.i.d - U（0, 1）, the p.d.f of 1 - Vk＋l be the GF of the unsigned Stirling numbers of the first kind s（n, k）. This paper discusses the applications of uniform distribution to combinatorial analysis and Riemann zeta function; several identities of Stifling series are established, and the Euler＇s result for ∑ Hn/n^k-l, k ≥ 3 is given a new probabilistic proof.     

On semi-infinite systems of linear inequalities

The ordered fieldR(M) consists of the realsR with a transcendentalM adjoined, which is larger than any realr ∈R. Given any semi-infinite matrix (s.i.m.) interpreted as linear inequalities:u ^tP_i≧c _i, ∀ _i ∈I, an arbitrary index set, it is also shown that the following are equivalent. (1) For every finiteJ ⊆I the systemu ^tP_i≧c _i,i ∈J is consistent, and (2) the s.i.m. has a solutionu ∈R(M) ⁿ. Some consequences for “duality gaps” are also given. These results were obtained as part of the activities of the Management Science Research Group and School of Urban and Public Affairs, Carnegie-Mellon University.     

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     

On the existence of invariant probability measures

Let (X,A) be a measureable space andT:X →X a measurable mapping. Consider a family ℳ of probability measures onA which satisfies certain closure conditions. IfA ₀⊂A is a convergence class for ℳ such that, for everyA ∈A ₀, the sequence ((1/n) Σ _i ^=0/n−1 1 _A ∘T ⁱ) converges in distribution (with respect to some probability measurev ∈ ℳ), then there exists aT-invariant element in ℳ. In particular, for the special case of a topological spaceX and a continuous mappingT, sufficient conditions for the existence ofT-invariant Borel probability measures with additional regularity properties are obtained.     

Comonotone approximation of twice differentiable periodic functions

In the case where a 2π-periodic function f is twice continuously differentiable on the real axis ℝ and changes its monotonicity at different fixed points y _i ∈ [− π, π), i = 1,…, 2s, s ∈ ℕ (i.e., on ℝ, there exists a set Y := {y _i } _i∈ℤ of points y _i = y _i+2s + 2π such that the function f does not decrease on [y _i , y _i−1] if i is odd and does not increase if i is even), for any natural k and n, n ≥ N(Y, k) = const, we construct a trigonometric polynomial T _n of order ≤n that changes its monotonicity at the same points y _i ∈ Y as f and is such that

On representation of the solution of the Neumann problem in a domain with peak by the harmonic simple layer potential

The problem of finding a solution of the Neumann problem for the Laplacian in the form of a simple layer potential Vρ with unknown density ρ is known to be reducible to a boundary integral equation of the second kind to be solved for density. The Neumann problem is examined in a bounded n-dimensional domain Ω⁺ (n > 2) with a cusp of an outward isolated peak either on its boundary or in its complement Ω⁻ = R ⁿ \Ω⁺. Let Γ be the common boundary of the domains Ω^±, Tr(Γ) be the space of traces on Γ of functions with finite Dirichlet integral over R ⁿ , and Tr(Γ)* be the dual space to Tr(Γ). We show that the solution of the Neumann problem for a domain Ω⁻ with a cusp of an inward peak may be represented as Vρ⁻, where ρ⁻ ∈ Tr(Γ)* is uniquely determined for all Ψ⁻ ∈ Tr(Γ)*. If Ω⁺ is a domain with an inward peak and if Ψ⁺ ∈ Tr(Γ)*, Ψ⁺ ⊥ 1, then the solution of the Neumann problem for Ω⁺ has the representation u ⁺ = Vρ⁺ for some ρ⁺ ∈ Tr(Γ)* which is unique up to an additive constant ρ₀, ρ₀ = V ⁻¹(1). These results do not hold for domains with outward peak.     

Controllability in a filled domain for the multidimensional wave equation with a singular boundary control

In accordance with the demands of the so-called local approach to inverse problems, the set of “waves” u^f (·, T) is studied, where u^f (x,t) is the solution of the initial boundary-value problem u_tt−Δu=0 in Ω×(0,T), u|_t<0=0, u|_∂Ω×(0,T)=f, and the (singular) control f runs over the class L²((0,T); H^−m (∂Ω)) (m>0). The following result is established. Let Ω^T={x ∈ Ω : dist(x, ∂Ω)<T)} be a subdomain of Ω ⊂ ℝⁿ (diam Ω<∞) filled with waves by a final instant of time t=T, let T_*=inf{T : Ω^T=Ω} be the time of filling the whole domain Ω. We introduce the notation D_m=Dom((−Δ)^m/2), where (−Δ) is the Laplace operator, Dom(−Δ)=H²(Ω)∩H ₀ ¹ (Ω);D_−m=(D_m)′;D_−m(Ω^T)={y∈D_−m:supp y ⋐ Ω^T. If T<T., then the reachable set R _m ^T ={u^t(·, T): f ∈ L₂((0,T), H^−m (∂Ω))} (∀m>0), which is dense in D_−m(Ω^T), does not contain the class C ₀ ^∞ (Ω^T). Examples of a ∈ C ₀ ^∞ , a ∈ R _m ^T , are presented. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 210, 1994, pp. 7–21. Translated by T. N. Surkova.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.