Decomposing <Emphasis Type="Italic">k</Emphasis>-ARc-Strong Tournaments Into Strong Spanning Subdigraphs

  The so-called Kelly conjecture states that every regular tournament on 2k+1 vertices has a decomposition into k-arc-disjoint hamiltonian cycles. In this paper we formulate a generalization of that conjecture, namely we conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs. We prove several results which support the conjecture:If D = (V, A) is a 2-arc-strong semicomplete digraph then it contains 2 arc-disjoint spanning strong subdigraphs except for one digraph on 4 vertices.Every tournament which has a non-trivial cut (both sides containing at least 2 vertices) with precisely k arcs in one direction contains k arc-disjoint spanning strong subdigraphs. In fact this result holds even for semicomplete digraphs with one exception on 4 vertices.Every k-arc-strong tournament with minimum in- and out-degree at least 37k contains k arc-disjoint spanning subdigraphs H ₁, H ₂, . . . , H _k such that each H _i is strongly connected.The last result implies that if T is a 74k-arc-strong tournament with speci.ed not necessarily distinct vertices u ₁, u ₂, . . . , u _k , v ₁, v ₂, . . . , v _k then T contains 2k arc-disjoint branchings where is an in-branching rooted at the vertex u _i and is an out-branching rooted at the vertex v _i , i=1,2, . . . , k. This solves a conjecture of Bang-Jensen and Gutin [3].We also discuss related problems and conjectures.

Every large set of equidistant (0, +1, −1)-vectors forms a sunflower

A theorem of Deza asserts that ifH ₁, ...,H _m ares-sets any pair of which intersects in exactlyd elements and ifm ≧s ² −s+2, then theH _i form aΔ-system, i.e. . In other words, every large equidistant (0, 1)-code of constant weight is trivial. We give a (0, +1, −1) analogue of this theorem.     

On the weighted Kneser-Poulsen conjecture

Suppose that p = (p1, p2, …, pN) and q = (q1, q2, …, qN) are two configurations in , which are centers of balls B ^d (p _i , r _i ) and B ^d (q _i , r _i ) of radius r _i , for i = 1, …, N. In [9] it was conjectured that if the pairwise distances between ball centers p are contracted in going to the centers q, then the volume of the union of the balls does not increase. For d = 2 this was proved in [1], and for the case when the centers are contracted continuously for all d in [2]. One extension of the Kneser-Poulsen conjecture, suggested in [6], was to consider various Boolean expressions in the unions and intersections of the balls, called flowers, where appropriate pairs of centers are only permitted to increase, and others are only permitted to decrease. Again under these distance constraints, the volume of the flower was conjectured to change in a monotone way. Here we show that these generalized Kneser-Poulsen flower conjectures are equivalent to an inequality between certain integrals of functions (called flower weight functions) over , where the functions in question are constructed from maximum and minimum operations applied to functions each being radially symmetric monotone decreasing and integrable. Research supported in part by NSF Grant No. DMS-0209595.     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.     

Maximal multilinear Calderón-Zygmund operators with non-doubling measures

Under the assumption that μ is a non-doubling measure on ℝ ^d which only satisfies some growth condition, the authors prove that the maximal multilinear Calderón-Zygmund operator is bounded from (μ) × … × (μ) into L ^p (μ) for any p ₁, … p _m ∈ (1, ∞) and p with 1/p = 1/p ₁ + … + 1/p _m , and bounded from (μ) × … × (μ) into weak- ^{L p} (μ) if there exists any p _i = 1. Furthermore, the authors establish a weighted weak-type estimate for the maximal multilinear Calderón-Zygmund operator. The second (corresponding) author is supported by Tianyuan Fund of China (No. 10626055) and National Natural Science Foundation of China (No. 10701078).     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

Small zeros of additive forms in several variables

Letf(X) be an additive form defined by

Dependent sets of a family of relations of full measure on a probability space

For a probability space (X, B,μ) a subfamily F of theσ-algebra B is said to be a regular base if every B∈B can be arbitrarily approached by some member of F which contains B in the sense of the measure theory. Assume that {γr}γ∈Γis a countable family of relations of the full measure on a probability space (X,B,μ), i.e. for everyγ∈Γthere is a positive integer sγsuch that Rγ(?)Xsγwithμsγ(Rγ) = 1. In the present paper we show that if (X, B,μ) has a regular base, the cardinality of which is not greater than the cardinality of the continuum, then there exists a set K(?)X withμ*(K) = 1 such that (x1,...,xsγ)∈γr for anyγ∈Γand for any sγdistinct elements x1,..., xsγof K, whereμ* is the outer measure induced by the measureμ. Moreover, an application of the result mentioned above is given to the dynamical systems determined by the iterates of measure-preserving transformations.     

Functoriality of automorphic <Emphasis Type="Italic">L</Emphasis>-functions through their zeros

Let E be a Galois extension of ℚ of degree l, not necessarily solvable. In this paper we first prove that the L-function L(s, π) attached to an automorphic cuspidal representation π of cannot be factored nontrivially into a product of L-functions over E. Next, we compare the n-level correlation of normalized nontrivial zeros of L(s, π₁)…L(s, π _k ), where π _j , j = 1,…, k, are automorphic cuspidal representations of , with that of L(s,π). We prove a necessary condition for L(s, π) having a factorization into a product of L-functions attached to automorphic cuspidal representations of specific , j = 1,…,k. In particular, if π is not invariant under the action of any nontrivial σ ∈ Gal _E/ℚ, then L(s, π) must equal a single L-function attached to a cuspidal representation of and π has an automorphic induction, provided L(s, π) can factored into a product of L-functions over ℚ. As E is not assumed to be solvable over ℚ, our results are beyond the scope of the current theory of base change and automorphic induction. Our results are unconditional when m,m ₁,…,m _k are small, but are under Hypothesis H and a bound toward the Ramanujan conjecture in other cases. The first author was supported by the National Basic Research Program of China, the National Natural Science Foundation of China (Grant No. 10531060), and Ministry of Education of China (Grant No. 305009). The second author was supported by the National Security Agency (Grant No. H98230-06-1-0075). The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein     

On conditions under which the sum of self-adjoint operators with given integer spectra is a scalar operator

We describe the set of parameters γ for which there exists a decomposition of the operator γI _H in a sum of n self-adjoint operators with spectra from the sets M ₁, …, M _n, M _i = 0, 1, …, k _i, for n ≥ 4 and, in some cases, for n = 3. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 4, pp. 470–477, April, 2008.     

Some trace formulae involving the split sequences of a Leonard pair

Let K denote a field, and let V denote a vector space over K with finite positive dimension. We consider a pair of linear transformations A : V → V and A^∗ : V → V that satisfy (i) and (ii) below:

(i)

There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A^∗ is irreducible tridiagonal and the matrix representing A is diagonal.

We call such a pair a Leonard pair on V. Let diag(θ₀, θ₁, … , θ_d) denote the diagonal matrix referred to in (ii) above and let denote the diagonal matrix referred to in (i) above. It is known that there exists a basis u₀, u₁, … , u_d for V and there exist scalars ?₁, ?₂, … , ?_d in K such that Au_i = θ_iu_i + u_i+1 (0 ? i ? d − 1), Au_d = θ_du_d, , . The sequence ?₁, ?₂, … , ?_d is called the first split sequence of the Leonard pair. It is known that there exists a basis v₀, v₁, … , v_d for V and there exist scalars ?₁, ?₂, … , ?_d in K such that Av_i = θ_d−iv_i + v_i+1 (0 ? i ? d − 1),Av_d = θ₀v_d, , . The sequence ?₁, ?₂, … , ?_d is called the second split sequence of the Leonard pair. We display some attractive formulae for the first and second split sequence that involve the trace function.     

Typical sheaves of generalized CM-modules

Let M be a generalized Cohen-Macaulay module over a noetherian local ring (R,m). Fix a standard system x₁, …, x_d∈m with respect to M and let . We construct a coherent Cohen-Macaulay sheafK over the projective space ℙ _R/I ^d-1 whose cohomological Hilbert functions depend only on the lengths of the local cohomology modules H _m ⁱ (M), (i=0, …, d−1).     

Degree series of the 3-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant λ such that the equality λd（vi） = Σ（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,..., ｜V（G）｜, where d（vi） denotes the degree of vertex vi. Let ni denote the number of vertices with degree i. This paper deals with the 3-Hgraphs and determines their degree series. Moreover, the 3-Hgraphs with bounded ni （1 ≤ i ≤ 7） are studied and some interesting results are obtained.     

Conditions for the existence of a graph with given diameter, connectivity, and ball diversity vector

Given some arbitrary integers d ≥ 2, ? ? 1 and an integer vector $ \bar \tau Given some arbitrary integers d ≥ 2, ϰ ⩾ 1 and an integer vector = (τ ₀, τ ₁, …, τ _d ) with τ ₀ ⩾ τ ₁ ⩾ … ⩾ τ _d = 1 and τ _{d − 1} ⩾ d ²ϰ + 3, the existence is proved of a graph of diameter d and connectivity ϰ whose ball diversity vector is . Moreover, the nonexistence is proved of a graph of diameter d with connectivity ϰ and ball diversity vector (τ ₀, τ ₁, …, τ _d ), where τ ₀ < (d − 1)ϰ + 2. Original Russian Text ? K.L. Rychkov, 2007, published in Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2007, Vol. 14, No. 4, pp. 43–56.     

Finitary reconstruction of a measure preserving transformation

This paper considers thefinitary reconstruction of an ergodic measure preserving transformationT of a complete separable metric spaceX from a single trajectoryx, Tx, …, or more generally, from a suitable reconstruction sequence x=x ₁,x ₂, … withx _i∈X. Ann-sample reconstruction is a functionT _n: X ⁿ⁺¹ →X; the map (·;x ₁, …,x _n)is treated as an estimate ofT(·) based on then initial elements of x. Given a reference probability measureμ ₀ and constantM>1, functionsT ₁,T ₂, … are defined, and it is shown that for everyμ with 1/M≤dμ/dμ ₀≤M, everyμ-preserving transformationT, and every reconstruction sequence x forT, the estimates (·;x ₁, …,x _nconverge toT in the weak topology. For the family of interval exchange transformations of [0, 1] a simple family of estimates is described and shown to be consistent both pointwise and in the strong topology. However, it is also shown that no finitary estimation scheme is consistent in the strong topology for the family of all ergodic Lebesgue measure preserving transformations of the unit interval, even if x is assumed to be a generic trajectory ofT. Supported in part by NSF Grant DMS-9501926.     

Inverse problem for zeros of certain koebe-related functions

If w₁,…,w _N is a finite sequence of nonzero points in the unit disk, then there are distinct points λ₁,…, λ_N on the unit circle and positive numbers Μ₁,…,Μ _N such that is the zero sequence of the function 1 — . The points λ₁,…, λ_N and numbers Μ₁,…,Μ_N are unique (except for reorderings).     

Matrices with the edmonds—Johnson property

A matrixA=(a _ij ) has theEdmonds—Johnson property if, for each choice of integral vectorsd ₁,d ₂,b ₁,b ₂, the convex hull of the integral solutions ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂ is obtained by adding the inequalitiescx≦|δ|, wherec is an integral vector andcx≦δ holds for each solution ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂. We characterize the Edmonds—Johnson property for integral matricesA which satisfy for each (row index)i. A corollary is that ifG is an undirected graph which does not contain any homeomorph ofK ₄ in which all triangles ofK ₄ have become odd circuits, thenG ist-perfect. This extends results of Boulala, Fonlupt, Sbihi and Uhry. First author’s research supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.).     

Balanced Leonard pairs

Let K denote a field, and let V denote a vector space over K with finite positive dimension. By a Leonard pair on V we mean an ordered pair of linear transformations A : V → V and A^∗ : V → V that satisfy the following two conditions:

(i)

There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A^∗ is irreducible tridiagonal and the matrix representing A is diagonal.

Let (respectively v₀, v₁, … , v_d) denote a basis for V that satisfies (i) (respectively (ii)). For 0 ? i ? d, let a_i denote the coefficient of , when we write as a linear combination of , and let denote the coefficient of v_i, when we write A^∗v_i as a linear combination of v₀, v₁, … , v_d.In this paper we show a₀ = a_d if and only if . Moreover we show that for d ? 1 the following are equivalent; (i) a₀ = a_d and a₁ = a_d−1; (ii) and ; (iii) a_i = a_d−i and for 0 ? i ? d. These give a proof of a conjecture by the second author. We say A, A^∗ is balanced whenever a_i = a_d−i and for 0 ? i ? d. We say A,A^∗ is essentially bipartite (respectively essentially dual bipartite) whenever a_i (respectively ) is independent of i for 0 ? i ? d. Observe that if A, A^∗ is essentially bipartite or dual bipartite, then A, A^∗ is balanced. For d ≠ 2, we show that if A, A^∗ is balanced then A, A^∗ is essentially bipartite or dual bipartite.     

Pseudo 1-homogeneous distance-regular graphs

Let Γ be a distance-regular graph of diameter d≥2 and a ₁≠0. Let θ be a real number. A pseudo cosine sequence for θ is a sequence of real numbers σ ₀,…,σ _d such that σ ₀=1 and c _i σ _i−1+a _i σ _i +b _i σ _i+1=θ σ _i for all i∈{0,…,d−1}. Furthermore, a pseudo primitive idempotent for θ is E _θ =s ∑ _i=0 ^d σ _i A _i , where s is any nonzero scalar. Let be the characteristic vector of a vertex v∈VΓ. For an edge xy of Γ and the characteristic vector w of the set of common neighbours of x and y, we say that the edge xy is tight with respect to θ whenever θ≠k and a nontrivial linear combination of vectors , and Ew is contained in . When an edge of Γ is tight with respect to two distinct real numbers, a parameterization with d+1 parameters of the members of the intersection array of Γ is given (using the pseudo cosines σ ₁,…,σ _d , and an auxiliary parameter ε). Let S be the set of all the vertices of Γ that are not at distance d from both vertices x and y that are adjacent. The graph Γ is pseudo 1-homogeneous with respect to xy whenever the distance partition of S corresponding to the distances from x and y is equitable in the subgraph induced on S. We show Γ is pseudo 1-homogeneous with respect to the edge xy if and only if the edge xy is tight with respect to two distinct real numbers. Finally, let us fix a vertex x of Γ. Then the graph Γ is pseudo 1-homogeneous with respect to any edge xy, and the local graph of x is connected if and only if there is the above parameterization with d+1 parameters σ ₁,…,σ _d ,ε and the local graph of x is strongly regular with nontrivial eigenvalues a ₁ σ/(1+σ) and (σ ₂−1)/(σ−σ ₂).     

Oscillation theorems for second-order nonlinear neutral delay dynamic equations on time scales

By employing the generalized Riccati transformation technique, we will establish some new oscillation criteria and study the asymptotic behavior of the nonoscillatory solutions of the second-order nonlinear neutral delay dynamic equation