On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset

Let P be a finite poset and H(P) be the hypergraph whose vertices are the points of P and whose edges are the maximal intervals in P. We study the domatic number d(G(P)) and the total domatic number d_t(G(P)) of the 2-section graph G(P) of H(P). For the subset P_l,u of P induced by consecutive levels of P, we give exact values of d(G(P_l,u)) when P is the chain product C_n1×C_n2. According to the values of l,u,n₁,n₂, the maximal domatic partition is exhibited. Moreover, we give some exact values or lower bounds for d(G(P∗Q)) and d_t(G(P_l,u)), when ∗ is the direct sum, the linear sum or the Cartesian product. Finally we show that the domatic number and the total domatic number problems in this class of graphs are NP-complete.     

Functional convergence of stochastic integrals with application to statistical inference

Assuming that {(U_n,V_n)} is a sequence of càdlàg processes converging in distribution to (U,V) in the Skorohod topology, conditions are given under which {?f_n(β,u,v)dU_ndV_n} converges weakly to ?f(β,x,y)dUdV in the space C(R), where f_n(β,u,v) is a sequence of “smooth” functions converging to f(β,u,v). Integrals of this form arise as the objective function for inference about a parameter β in a stochastic model. Convergence of these integrals play a key role in describing the asymptotics of the estimator of β which optimizes the objective function. We illustrate this with a moving average process.     

The supertail of a subspace partition

Let V = V(n, q) be a vector space of dimension n over the finite field with q elements, and let d ₁ < d ₂ < ... < d _m be the dimensions that occur in a subspace partition ${\mathcal{P}}$ of V. Let σ _q (n, t) denote the minimum size of a subspace partition ${\mathcal P}$ of V, in which t is the largest dimension of a subspace. For any integer s, with 1 < s ≤ m, the set of subspaces in ${\mathcal{P}}$ of dimension less than d _s is called the s-supertail of ${\mathcal{P}}$ . The main result is that the number of spaces in an s-supertail is at least σ _q (d _s , d _s?1).     

On a Conjecture on Directed Cycles in a Directed Bipartite Graph

Let D = (V ₁, V ₂; A) be a directed bipartite graph with |V ₁| = |V ₂| = n ≥ 2. Suppose that d _D (x) + d _D (y) ≥ 3n for all x ∈ V ₁ and y ∈ V ₂. Then, with one exception, D contains two vertex-disjoint directed cycles of lengths 2n ₁ and 2n ₂, respectively, for any positive integer partition n = n ₁ + n ₂. This proves a conjecture proposed in [9].     

Inversion formulas for complex radon transform on projective varieties and boundary value problems for systems of linear PDEs

Let G ? ?P ⁿ be a linearly convex compact set with smooth boundary, D = ?P ⁿ \ G, and let D* ? (?P ⁿ )* be the dual domain. Then for an algebraic, not necessarily reduced, complete intersection subvariety V of dimension d we construct an explicit inversion formula for the complex Radon transform R _V : H ^d,d?1(V ∩ D) → H ^1,0(D*) and explicit formulas for solutions of an appropriate boundary value problem for the corresponding system of differential equations with constant coefficients on D*.     

On the metrizability of cone metric spaces

We have shown in this paper that a (complete) cone metric space (X,E,P,d) is indeed (completely) metrizable for a suitable metric D. Moreover, given any finite number of contractions f₁,…,fn on the cone metric space (X,E,P,d), D can be defined in such a way that these functions become also contractions on (X,D).     

Normal connections induced by a framed hypersurface in the conformal space

We find two normal connections induced by the normal framing of a hypersurface V _{n ? 1} in the conformal space C _n , and establish relationship between these connections and a Weyl connection which is also induced by the normal framing of V _{n ? 1}. We study two normal connections induced by a complete framing of a hypersurface V _{n ? 1} in C _n . We establish relationship between geometries of a framed hypersurface V _{n ? 1} of the conformal space C _n and a quadratic hyperband of the projective space P _{n + 1} associated with V _{n ? 1}.     

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

Given a complete k-partite graph G=(V₁,V₂,…,V_k;E) satisfying |V₁|=|V₂|=?=|V_k|=n and weights of all  k-cliques of G, the  k-dimensional assignment problem finds a partition of vertices of G into a set of (pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q^d and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k) of the approximation ratio.     

On Ranks of Polynomials

Let V be a vector space over a field k, P : V → k, d ≥?3. We show the existence of a function C(r, d) such that rank(P) ≤ C(r, d) for any field k, char(k) > d, a finite-dimensional k-vector space V and a polynomial P : V → k of degree d such that rank(?P/?t) ≤ r for all t ∈ V ??0. Our proof of this theorem is based on the application of results on Gowers norms for finite fields k. We don’t know a direct proof even in the case when k = ?.     

Recent results on designs with classical parameters

We report on recent results concerning designs with the same parameters as the classical geometric designs PG _d (n, q) formed by the points and d-dimensional subspaces of the n-dimensional projective space PG(n, q) over the field GF(q) with q elements, where 1 ???d ???n?1. The corresponding case of designs with the same parameters as the classical geometric designs AG _d (n, q) formed by the points and d-dimensional subspaces of the n-dimensional affine space AG(n, q) will also be discussed, albeit in less detail.     

Topological obstructions for vertex numbers of Minkowski sums

We show that for polytopes P₁,P₂,…,Pr⊂Rd, each having ni?d+1 vertices, the Minkowski sum P₁+P₂+?+Pr cannot achieve the maximum of i_∏ni vertices if r?d. This complements a recent result of Fukuda and Weibel (2006), who show that this is possible for up to d−1 summands. The result is obtained by combining methods from discrete geometry (Gale transforms) and topological combinatorics (van Kampen-type obstructions).     

Properties of Regular Uniform k—Stratified Graphs

A regular graph G = (V, E) is a k-stratified graph if V is partitioned into V₁, V₂, …, V_k subsets called strata. The stratification splits the degree d_v ∀v ϵ V into k-integers d_v1, d_v2, …, d_vk each one corresponding to a stratum. If d_v1 = d_v2 = … = d_vk ∀v ϵ V then G is called regular uniform k-stratified, RU^k_s(n, d) where n is the cardinality of the vertex set in each stratum and d is the degree of every vertex in each stratum. For every k, the class RU^k_s(n, d) has a unique graph generator class RU^l_s(n, d) derived by decomposition of graphs in RU^k_s(n, d). We investigate the minimization of the cardinality of V, the colorability, vertex coloring and the diameter of the graphs in the class. We also deal with complexity questions concerning RU^k_s(n, d). Some well-known computer network models such as barrel shifters and hypercubes are shown to belong in RU^k_s(n, d).     

COMPUTING THE SPREADING AND COVERING NUMBERS

Let S = k[x ₁,…,x _n ], d a positive integer, and suppose that S _D is the vector space of all polynomials of degree d in S. Define α _n (d) ? max { dim _k V| V monomial subspace of S _d , dim _k S ₁ V = n dim _k V} and ρ _n (d +1) ? min {dim _k V | V monomial subspace of S _d , S ₁ V = S _d+1}. The numbers α _n (d) and ρ _n (d+ 1) are called the spreading numbers and covering numbers, respectively. We describe an approach to calculate these numbers that uses simplicial complexes.     

On metric spaces with the Haver property which are Menger spaces

A metric space (X,d) has the Haver property if for each sequence ?₁,?₂,… of positive numbers there exist disjoint open collections V₁,V₂,… of open subsets of X, with diameters of members of Vi less than ?i and covering X, and the Menger property is a classical covering counterpart to σ-compactness. We show that, under Martin's Axiom MA, the metric square (X,d)×(X,d) of a separable metric space with the Haver property can fail this property, even if X² is a Menger space, and that there is a separable normed linear Menger space M such that (M,d) has the Haver property for every translation invariant metric d generating the topology of M, but not for every metric generating the topology. These results answer some questions by L. Babinkostova [L. Babinkostova, When does the Haver property imply selective screenability? Topology Appl. 154 (2007) 1971-1979; L. Babinkostova, Selective screenability in topological groups, Topology Appl. 156 (1) (2008) 2-9].     

On the localization of binding for Schrödinger operators and its extension to elliptic operators

In this paper we study the asymptotic behavior of the ground state energyE(R) of the Schrödinger operatorP _R=?Δ+V ₁(x)+V ₂(x-R),x,R ∈?ⁿ, where the potentialsV _i are small perturbations of the Laplacian in ?ⁿ,n≥3. The methods presented here apply also in the investigation of the ground state energyE(g) of the operatorPg=P+V ₁(x)+V ₂(gx), x ∈X,g ∈G, whereP _g is an elliptic operator which is defined on a noncompact manifoldX, G is a discrete group acting onX by diffeomorphismsG×X∈(g, x)→gx∈X, andP is aG-invariant elliptic operator which is subcritical inX.     

Generalization of matching extensions in graphs (III)

Proposing them as a general framework, Liu and Yu (2001) [6] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d+2?|V(G)| and |V(G)|−n−d is even. If on deleting any n vertices from G the remaining subgraph H of G contains a k-matching and each k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. In this paper, we obtain more properties of (n,k,d)-graphs, in particular the recursive relations of (n,k,d)-graphs for distinct parameters n,k and d. Moreover, we provide a characterization for maximal non-(n,k,d)-graphs.     

On the irreducibility of multivariate subresultants

Let P₁,…,P_n be generic homogeneous polynomials in n variables of degrees d₁,…,d_n respectively. We prove that if ν is an integer satisfying ∑_i=1ⁿd_i?n+1?min{d_i}<ν, then all multivariate subresultants associated to the family P₁,…,P_n in degree ν are irreducible. We show that the lower bound is sharp. As a byproduct, we get a formula for computing the residual resultant of $\text{ρ?ν+n?1}\text{n?1}$ smooth isolated points in $\text{P}{}^{\mathrm{<mspace\; sp="0.2"\; width="2px"\; linebreak="nobreak"\; is="true"></mspace><mtext>n?1</mtext>}}\text{.}$To cite this article: L. Busé, C. D'Andrea, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.