Nombre de representations d'une permutation comme produit de deux cycles de longueurs donnees

We consider the Ramsey number r(sK₂, G) where sK₂(s?1) denotes a set of s disjoint edges and G is an arbitrary finite simple graph with no isolated vertices. We obtain upper and lower bounds in the general case. Exact results are obtained for certain classes of graphs.     

Towards an inverse scattering theory for two-dimensional nondecaying potentials

The inverse scattering method is considered for the nonstationary Schrödinger equation with the potentialu (x ₁,x ₂) nondecaying in a finite number of directions in thex plane. The general resolvent approach, which is particularly convenient for this problem, is tested using a potential that is the Bäcklund transformation of an arbitrary decaying potential and that describes a soliton superimposed on an arbitrary background. In this example, the resolvent, Jost solutions, and spectral data are explicitly constructed, and their properties are analyzed. The characterization equations satisfied by the spectral data are derived, and the unique solution of the inverse problem is obtained. The asymptotic potential behavior at large distances is also studied in detail. The obtained resolvent is used in a dressing procedure to show that with more general nondecaying potentials, the Jost solutions may have an additional cut in the spectral-parameter complex domain. The necessary and sufficient condition for the absence of this additional cut is formulated.     

An algorithm for the number of path homomorphisms

A homomorphism of a graph G₁=(V₁,E₁) to a graph G₂=(V₂,E₂) is a mapping from the vertex set V₁ of G₁ to the vertex set V₂ of G₂ which preserves edges. In this paper we provide an algorithm to determine the number of homomorphisms from an arbitrary finite undirected path to another arbitrary finite undirected path.     

Intersections of Schubert varieties and eigenvalue inequalities in an arbitrary finite factor

The intersection ring of a complex Grassmann manifold is generated by Schubert varieties, and its structure is governed by the Littlewood-Richardson rule. Given three Schubert varieties S₁, S₂, S₃ with intersection number equal to one, we show how to construct an explicit element in their intersection. This element is obtained generically as the result of a sequence of lattice operations on the spaces of the corresponding flags, and is therefore well defined over an arbitrary field of scalars. Moreover, this result also applies to appropriately defined analogues of Schubert varieties in the Grassmann manifolds associated with a finite von Neumann algebra. The arguments require the combinatorial structure of honeycombs, particularly the structure of the rigid extremal honeycombs. It is known that the eigenvalue distributions of self-adjoint elements a,b,c with a+b+c=0 in the factor Rω are characterized by a system of inequalities analogous to the classical Horn inequalities of linear algebra. We prove that these inequalities are in fact true for elements of an arbitrary finite factor. In particular, if x,y,z are self-adjoint elements of such a factor and x+y+z=0, then there exist self-adjoint a,b,c∈Rω such that a+b+c=0 and a (respectively, b,c) has the same eigenvalue distribution as x (respectively, y,z). A (‘complete’) matricial form of this result is known to imply an affirmative answer to an embedding question formulated by Connes. The critical point in the proof of this result is the production of elements in the intersection of three Schubert varieties. When the factor under consideration is the algebra of n×n complex matrices, our arguments provide new and elementary proofs of the Horn inequalities, which do not require knowledge of the structure of the cohomology of the Grassmann manifolds.     

Equivalence relations in the approximations for the M/G/s/s + r queue

This paper investigates some equivalence relations among previously established approximations for the steady-state distribution in an M/G/s queue with finite waiting spaces. The focus is on four approximations developed by Hokstad [1], Tijms and van Hoorn [2], Miyazawa [3] and Kimura [4]. These approximations have been obtained by completely different approaches and they have different expressions. Equivalence theorems show conditions under which some of the approximations coincide.     

A graph-theoretic approach to quasigroup cycle numbers

Norton and Stein associated a number with each idempotent quasigroup or diagonalized Latin square of given finite order n, showing that it is congruent mod 2 to the triangular number T(n). In this paper, we use a graph-theoretic approach to extend their invariant to an arbitrary finite quasigroup. We call it the cycle number, and identify it as the number of connected components in a certain graph, the cycle graph. The congruence obtained by Norton and Stein extends to the general case, giving a simplified proof (with topology replacing case analysis) of the well-known congruence restriction on the possible orders of general Schroeder quasigroups. Cycle numbers correlate nicely with algebraic properties of quasigroups. Certain well-known classes of quasigroups, such as Schroeder quasigroups and commutative Moufang loops, are shown to maximize the cycle number among all quasigroups belonging to a more general class.     

Banded matrices with banded inverses,II: Locally finite decomposition of spline spaces

Given two function spacesV ₀,V ₁ with compactly supported basis functionsC _i, F_i, i∈Z, respectively, such thatC _i can be written as a finite linear combination of theF _i's, we study the problem of decomposingV ₁ into a direct sum ofV ₀ and some subspaceW ofV ₁ in such a way thatW is spanned by compactly supported functions and that eachF _i can be written as a finite linear combination of the basis functions inV ₀ andW. The problem of finding such locally finite decompositions is shown to be equivalent to solving certain matrix equations involving two-slanted matrices. These relations may be reinterpreted in terms of banded matrices possessing banded inverses. Our approach to solving the matrix equations is based on factorization techniques which work under certain conditions on minors. In particular, we apply these results to univariate splines with arbitrary knot sequences.     

An extremal problem for finite topologies and distributive lattices

Let (r₁, r₂, …) be a sequence of non-negative integers summing to n. We determine under what conditions there exists a finite distributive lattice L of rank n with r_i join-irreducibles of rank i, for all i = 1, 2, …. When L exists, we give explicit expressions for the greatest number of elements L can have of any given rank, and for the greatest total number of elements L can have. The problem is also formulated in terms of finite topological spaces.     

Simultaneous effects of partial slip and thermal-diffusion and diffusion-thermo on steady MHD convective flow due to a rotating disk

The purpose of present research is to derive analytical expressions for the solution of steady MHD convective and slip flow due to a rotating disk. Viscous dissipation and Ohmic heating are taken into account. The nonlinear partial differential equations for MHD laminar flow of the homogeneous fluid are reduced to a system of five coupled ordinary differential equations by using similarity transformation. The derived solution is expressed in series of exponentially-decaying functions using homotopy analysis method (HAM). The convergence of the obtained series solutions is examined. Finally some figures are sketched to show the accuracy of the applied method and assessment of various slip parameter γ, magnetic field parameter M, Eckert Ec, Schmidt Sc and Soret Sr numbers on the profiles of the dimensionless velocity, temperature and concentration distributions. Validity of the obtained results are verified by the numerical results.     

Small subgraphs in random graphs and the power of multiple choices

The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with G₀ as the empty graph on n vertices, in every step a set of r edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining r−1 edges are discarded. Thus after N steps, we have seen rN edges, and selected exactly N out of these to create a graph GN.In a recent paper by Krivelevich, Loh, and Sudakov (2009) [11], the problem of avoiding a copy of some fixed graph F in GN for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs F. In this work we disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions N₀(F,r,n) for arbitrary graphs F and any fixed integer r. That is, we propose an edge selection strategy that a.a.s. (asymptotically almost surely, i.e. with probability 1−o(1) as n→∞) avoids creating a copy of F for as long as N=o(N₀), and prove that any online strategy will a.a.s. create such a copy once N=ω(N₀).     

On spectral theory in discrete programming: References added in proof

In different parts of discrete programming so-called (H,A,L_C)-problems are studied, where one must find an h_o?H (H is a set of permutation), for which L_C(h_o) = min_h?HL_C(h), L_C(h) = c_1h(1) +...+ c_nh(n), C = | c_ij | is an n ×n-matrix over A, and A is a totally ordered commutative semigroup (for example, semigroup of positive real numbers or a finite commutative totally ordered semigroup). We are dealing with the full spectrum of values of the function L_C and not only with the solutions of a (H,A,L_C)-problem. Equivalence theorems for different classes of these problems are proved. Realizability of spectra in some classes of (H,A,L_C)-problems is studied.     

Stokes constants of an oblate ellipsoid of revolution with equidensites homothetic to its surface

The theory of equilibrium figures was actively developed in the 19th century, when it was found that the observed massive celestial bodies (the Sun, planets, and satellites) had an almost ellipsoidal form. The existence of exactly ellipsoidal figures was also established. The gravitational potential of these figures is represented by a Laplace series with its coefficients (Stokes’ constants I _n ) determined by some integral operator. The general term of the series was found for a homogeneous ellipsoid of revolution and the first terms of the series were found for some other mass distributions. Here, we have obtained the general term of the series for an arbitrary mass distribution given that the equidensites (surfaces of equal density) are homothetic to the outer surface of the ellipsoid of revolution. Simple estimates and an asymptotics of I _n have also been obtained.     

Asymptotics of the probability of values of random Boolean expressions

The random Boolean expressions are considered that are obtained by the random and independent substitution with the probabilities p and 1 ? p of the constantly one function and constantly zero function for variables of repetition-free formulas over a given basis. The probability is studied that the expressions are equal to one. It is shown that, for each finite basis and p ? (0, 1), this probability tends to some finite limit P ₁(p) as the length of an expression grows. Explicit representation of the probability function P ₁(p) is found for all finite bases, the analytic properties of this function are studied, and its behavior is investigated in dependence on the properties of the basis.     

On Mardia's and Song's measures of kurtosis in elliptical distributions

The main objective of this paper is the calculation and the comparative study of two general measures of multivariate kurtosis, namely Mardia's measure β_2,p and Song's measure S(f). In this context, general formulas for the said measures are derived for the broad family of the elliptically contoured symmetric distributions and also for specific members of this family, like the multivariate t-distribution, the multivariate Pearson type II, the multivariate Pearson type VII, the multivariate symmetric Kotz type distribution and the uniform distribution in the unit sphere. Analytic expressions for computing Shannon and Rényi entropies are obtained under the elliptic family. The behaviour of Mardia's and Song's measures, their similarities and differences, possible interpretations and uses in practice are investigated by comparing them in specific members of the elliptic family of multivariate distributions. An empirical estimator of Song's measure is moreover proposed and its asymptotic distribution is investigated under the elliptic family of multivariate distributions.     

Linear syzygies and birational combinatorics

Let F be a finite set of monomials of the same degree d ≥ 2 in a polynomial ring R = k[x ₁,…, x _n ] over an arbitrary field k. We give some necessary and/or sufficient conditions for the birationality of the ring extension k[F] ? R ^(d), where R ^(d) is the dth Veronese subring of R. One of our results extends to arbitrary characteristic, in the case of rational monomial maps, a previous syzygytheoretic birationality criterion in characteristic zero obtained in [1].     

On the normalizers of subalgebras in an infinite Lie algebra

An algorithm for calculating the normalizer of subalgebra in an infinite Lie symmetry algebra is proposed. The classification problem for a subalgebra spanned by generators that depend on arbitrary functions is formulated. This problem lies in finding the specifications of arbitrary functions and calculating the normalizers of the subalgebras so obtained. As an example, we consider the Lie symmetry algebra L admitted by the thermal diffusion equations. The first-order optimal system of subalgebras Θ₁L is constructed and the normalizers of finite subalgebras from this system are found. The classification of subalgebras depending on arbitrary functions is made.     

Best constants for metric space inversion inequalities

For every metric space (X, d) and origin o ∈ X, we show the inequality I _o (x, y) ≤ 2d _o (x, y), where I _o (x, y) = d(x, y)/d(x, o)d(y, o) is the metric space inversion semimetric, d _o is a metric subordinate to I _o , and x, y ∈ X \ {o} The constant 2 is best possible.     

Uniform approximation of continuous functions by probability functions of Boolean bases

Random Boolean expressions obtained by random and independent substitution of the constants 1, 0 with probabilities p, 1 ? p, respectively, into random non-iterated formulas over a given basis are considered. The limit of the probability of appearance of expressions with the value 1 under unrestricted growth of the complexity of expressions, which is called the probability function, is considered. It is shown that for an arbitrary continuous function f(p) mapping the segment [0, 1] into itself there exists a sequence of bases whose probability functions uniformly approximate the function f(p) on the segment [0, 1].     

Higher-order recurrences for Bernoulli numbers

Euler's well-known nonlinear relation for Bernoulli numbers, which can be written in symbolic notation as n(B₀+B₀)=−nBn−1−(n−1)Bn, is extended to n(Bk₁+?+Bkm) for m?2 and arbitrary fixed integers k₁,…,km?0. In the general case we prove an existence theorem for Euler-type formulas, and for m=3 we obtain explicit expressions. This extends the authors' previous work for m=2.     

2K2 vertex-set partition into nonempty parts

A graph is 2K₂-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K₂-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We show that for C₄-free graphs, circular-arc graphs, spiders, P₄-sparse graphs, and bipartite graphs the 2K₂-partition problem can be solved in polynomial time.