Geometry of isotypic Kronecker webs

An isotypic Kronecker web is a family of corank m foliations such that the curve of annihilators t ↦ (T _x F _t )^⊥ ∈ Gr _m (T _x * M) is a rational normal curve in the Grassmannian Gr _m (T _x *M) at any point x ∈ M. For m = 1 we get Veronese webs introduced by I. Gelfand and I. Zakharevich [Gelfand I.M., Zakharevich I., Webs, Veronese curves, and bi-Hamiltonian systems, J. Funct. Anal., 1991, 99(1), 150–178]. In the present paper, we consider the problem of local classification of isotypic Kronecker webs and for a given web we construct a canonical connection. We compute the curvature of the connection in the case of webs of equal rank and corank. We also show the correspondence between Kronecker webs and systems of ODEs for which certain sets of differential invariants vanish. The equations are given up to contact transformations preserving independent variable. As a particular case, with m = 1 we obtain the correspondence between Veronese webs and ODEs.     

Nonexistence of Proper Holomorphic Maps Between Certain Classical Bounded Symmetric Domains

The author,motivated by his results on Hermitian metric rigidity,conjectured in [4] that a proper holomorphic mapping f：Ω→Ω′from an irreducible bounded symmetric domainΩof rank≥2 into a bounded symmetric domainΩ′is necessarily totally geodesic provided that r′：=rank（Ω′）≤rank（Ω）：=r.The Conjecture was resolved in the affirmative by I.-H.Tsai [8].When the hypothesis r′≤r is removed,the structure of proper holomorphic maps f：Ω→Ω′is far from being understood,and the complexity in studying such maps depends very much on the difference r′-r,which is called the rank defect.The only known nontrivial non-equidimensional structure theorems on proper holomorphic maps are due to Z.-H.Tu [10],in which a rigidity theorem was proven for certain pairs of classical domains of type I,which implies nonexistence theorems for other pairs of such domains.For both results the rank defect is equal to 1,and a generaliza- tion of the rigidity result to cases of higher rank defects along the line of arguments of [10] has so far been inaccessible. In this article, the author produces nonexistence results for infinite series of pairs of （Ω→Ω′） of irreducible bounded symmetric domains of type I in which the rank defect is an arbitrarily prescribed positive integer. Such nonexistence results are obtained by exploiting the geometry of characteristic symmetric subspaces as introduced by N. Mok and L-H Tsai [6] and more generally invariantly geodesic subspaces as formalized in [8]. Our nonexistence results motivate the formulation of questions on proper holomorphic maps in the non-equirank case.     

(2,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4]. Received: December 16, 1996 / Revised: September 17, 1997     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Combinatorial obstructions to the lifting of weaving diagrams

This paper deals with various connections of oriented matroids [3] and weaving diagrams of lines in space [9], [16], [27]. We encode the litability problem of a particular weaving diagramD onn lines by the realizability problem of a partial oriented matroid χ _D with2n elements in rank 4. We prove that the occurrence of a certain substructure inD implies that χD is noneuclidean in the sense of Edmonds, Fukuda, and Mandel [12], [14]. Using this criterion we construct an infinite class of minor-minimal noneuclidean oriented matroids in rank 4. Finally, we give an easy algebraic proof for the nonliftability of the alternating weaving diagram on a bipartite grid of 4×4 lines [16].     

A consistent value for games with n players and r alternatives

In Bolger [1993], an efficient value was obtained for a class of games called games with n players and r alternatives. In these games, each of the n players must choose one and only one of the r alternatives. This value can be used to determine a player’s “a priori” value in such a game. In this paper, we show that the value has a consistency property similar to the “consistency” for TU games in Hart/Mas-Colell [1989] and we present a set of axioms (including consistency) which characterizes this value.  The games considered in this paper differ from the multi-choice games considered by Hsiao and Raghavan [1993]. They consider games in which the actions of the players are ordered in the sense that, if i >j, then action i carries more “weight” than action j.  These games also differ from partition function games in that the worth of a coalition depends not only on the partitioning of the players but also on the action chosen by each subset of the partition. Received: April 1994/final version: June 1999     

Differential-geometric structures on generalized Reidemeister and Bol three-webs

In this paper, we present the main results of the study of multidimensional three-websW(p, q, r) obtained by the method of external forms and moving Cartan frame. The method was developed by the Russian mathematicians S. P. Finikov, G. F. Laptev, and A. M. Vasiliev, while fundamentals of differential-geometric (p, q, r)-webs theory were described by M. A. Akivis and V. V. Goldberg. Investigation of (p, q, r)-webs, including algebraic and geometric theory aspects, has been continued in our papers, in particular, we found the structure equations of a three-web W(p, q, r), where p = λl, q = λm, and r = λ(l + m − 1). For such webs, we define the notion of a generalized Reidemeister configuration and proved that a three-web W(λl, λm, λ(l + m − 1)), on which all sufficiently small generalized Reidemeister configurations are closed, is generated by a λ-dimensional Lie group G. The structure equations of the web are connected with the Maurer–Cartan equations of the group G. We define generalized Reidemeister and Bol configurations for three-webs W(p, q, q). It is proved that a web W(p, q, q) on which generalized Reidemeister or Bol configurations are closed is generated, respectively, by the action of a local smooth q-parametric Lie group or a Bol quasigroup on a smooth p-dimensional manifold. For such webs, the structure equations are found and their differential-geometric properties are studied.     

Transversals in Uniform Hypergraphs with Property (p,2)

Dedicated to the memory of Paul Erdős Let f(r,p,t) (p > t >= 1, r >= 2) be the maximum of the cardinality of a minimum transversal over all r-uniform hypergraphs possessing the property that every subhypergraph of with p edges has a transversal of size t. The values of f(r,p,2) for p = 3, 4, 5, 6 were found in [1] and bounds on f(r,7,2) are given in [3]. Here we prove that for large p and huge r. Received September 23, 1999 RID="*" ID="*" This work was partially supported by the grant 99-01-00581 of the Russian Foundation for Fundamental Research and the Dutch–Russian Grant NWO-047-008-006.     

New upper bounds for the Davenport and for the Erdős–Ginzburg–Ziv constants

Let G be a finite abelian group (written additively) of rank r with invariants n ₁, n ₂, . . . , n _r , where n _r is the exponent of G. In this paper, we prove an upper bound for the Davenport constant D(G) of G as follows; D(G) ≤ n _r + n _r-1 + (c(3) − 1)n _r-2 + (c(4) − 1) n _r-3 + · · · + (c(r) − 1)n ₁ + 1, where c(i) is the Alon–Dubiner constant, which depends only on the rank of the group \mathbb Z_nrⁱ{{\mathbb Z}_{n_r}^i}. Also, we shall give an application of Davenport’s constant to smooth numbers related to the Quadratic sieve.     

Semi-parametric Estimation of the Hölder Exponent of a Stationary Gaussian Process with Minimax Rates

Let (X(t))_t∈[0,1] be a centered Gaussian process with stationary increments such that IE[(X_{u+t-X_u)²] = C|t|^s+r(t). Assume that there exists an extra parameter β > 0 and a polynomial P of degree smaller than s + β such that |r(t)-P(t)| is bounded with respect to |t|^s+β. We consider the problem of estimating the parameter s ∈ (0,2) in the asymptotic framework given by n equispaced observations in [0, 1]. Adding possibly stronger regularity conditions to r, we define classes of such processes over which we show that s cannot be estimated at a better rate than n^{min(1/2, β)}. Then, we study increment (or, more generally, discrete variation) estimators. We obtained precise bounds of the bias of the variance which show that the bias mainly depend on the parameter β and the variance on two terms, one depending on the parameter s and one on some regularity properties of r. A central limit theorem is given when the variance term relying on s dominates the bias and the other variance term. Eventually, we exhibit an estimator which achieves the minimax rate over a wide range of classes for which sufficient regularity conditions are assumed on r. This revised version was published online in August 2006 with corrections to the Cover Date.     

On some Fano manifolds of large pseudoindex

In this paper we classify pairs (X,ℰ) with ℰ ample vector bundle of rank r on a smooth variety X of dimension n= 2r−1 such that K _X + det ℰ=? _x . Received: 7 April 2000     

Abelian functional equations, planar web geometry and polylogarithms

We study some abelian functional equations (Afe). They are equations in the F_i’s of the form F₁(U₁) + ... + F_N(U_N) = 0 where the U_i’s are real rational functions in two variables. First we prove that the local measurable solutions are actually analytic and we characterize their components as solutions of linear differential equations constructed from the U_i’s. Then we propose two methods for solving Afe. Next we apply these methods to the explicit resolution of generalized versions of classical (inhomogeneous) Afe satisfied by low order polylogarithms. Interpreted in the framework of web geometry, these results give us new nonlinearizable maximal rank planar webs. Then we observe that there is a relation between these webs and certain configurations of points in which leads us to define the notion of web associated to a configuration: these webs seem of high rank and could provide numerous new exceptional webs. Finally, we use the preceding results to show that, under weak regularity assumptions, the trilogarithm is the only function which satisfies the Spence–Kummer equation.     

Invariant differential operators on symplectic grassmann manifolds

LetM _2n,r denote the vector space of real or complex2n×r matrices with the natural action of the symplectic group Sp _2n , and letG=G _n,r =Sp _2n ×M _2n,r denote the corresponding semi-direct product. For any integerp with 0≤p≤n−1, letH denote the subgroupG _p,r ×Sp _2n−2p ofG. We explicitly compute the algebra of left invariant differential operators onG/H, and we show that it is a free algebra if and only ifr≤2n−2p+1. We also give orthogonal analogues of these results, generalizing those of Gonzalez and Helgason [3]. Partially supported by NSF grant DMS-9101358 This article was processed by the author using the Springer-Verlag T_EX mamath macro package 1990.     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999     

Oriented matroids with few mutations

This paper defines a “connected sum” operation on oriented matroids of the same rank. This construction is used for three different applications in rank 4. First it provides nonrealizable pseudoplane arrangements with a low number of simplicial regions. This contrasts the case of realizable hyperplane arrangements: by a classical theorem of Shannon every arrangement ofn projective planes in ℝP ^d-1 contains at leastn simplicial regions and every plane is adjacent to at leastd simplicial regions [17], [18]. We construct a class of uniform pseudoarrangements of 4n pseudoplanes in ℝP³ with only 3n+1 simplicial regions. Furthermore, we construct an arrangement of 20 pseudoplanes where one plane is not adjacent to any simplicial region. Finally we disprove the “strong-map conjecture” of Las Vergnas [1]. We describe an arrangement of 12 pseudoplanes containing two points that cannot be simultaneously contained in an extending hyperplane.     

A Note on the Homology of Signed Posets

Let S be a signed poset in the sense of Reiner [4]. Fischer [2] defines the homology of S, in terms of a partial ordering P (S) associated to S, to be the homology of a certain subcomplex of the chain complex of P (S).In this paper we show that if P (S) is Cohen-Macaulay and S has rank n, then the homology of S vanishes for degrees outside the interval [n/2, n].Research partially supported by the National Science Foundation and the John Simon Guggenheim Foundation.     

Commutator equations in free groups

Letf ₁, …,f _n be free generators of a free groupF. We consider the equation [z ₁, …,z _n]_ω. where ω and ω′ indicate the disposition of brackets in the higher commutators [z ₁, …,z _n]_ω and [f ₁, …,f _n]_ω. We give a necessary and sufficient condition on ω and ω′ for the existence of solutions of this equation. It is also shown that for any solutionz ₁=r₁, …,z _z=r _n we have <r ₁, …,r _n>=〈f ₁, …f _n〉.     

On the Construction of Permutation Arrays via Mappings from Binary Vectors to Permutations

An (n, d, k)-mapping f is a mapping from binary vectors of length n to permutations of length n + k such that for all x, y {0,1}ⁿ, d_H (f(x), f(y)) ≥ d_H (x, y) + d, if d_H (x, y) ≤ (n + k) − d and d_H (f(x), f(y)) = n + k, if d_H (x, y) > (n + k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n ≥ 6. An (n, r)-permutation array is a permutation array of length n and any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n ≥ 8, P(n, r) ≥ A(n − 2, r − 3) > A(n − 1,r − 2) = A(n, r − 1) when n is even and P(n, r) ≥ A(n − 2, r − 3) = A(n − 1, r − 2) > A(n, r − 1) when n is odd. This improves the best bound A(n − 1,r − 2) so far [Huang et al. (submitted)] for n ≥ 8. The work was supported in part by the National Science Council of Taiwan under contract NSC-93-2213-E-009-117     

A criterion for regular sequences

LetR be a commutative noetherian ring and ƒ₁, …, ƒ_r ∃ R. In this article we give (cf. the Theorem in §2) a criterion for ƒ₁, …, ƒ_r to be regular sequence for a finitely generated module overR which strengthens and generalises a result in [2]. As an immediate consequence we deduce that if V(g ₁, …,g _r ) ⊆ V(ƒ₁, …, ƒ_r) in SpecR and if ƒ₁, …, ƒ_r is a regular sequence inR, theng ₁, …,g _r is also a regular sequence inR.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.