Probabilistic stable rules and Nash equilibrium in two-sided matching problems

We study many-to-many matching with substitutable and cardinally monotonic preferences. We analyze stochastic dominance (sd) Nash equilibria of the game induced by any probabilistic stable matching rule. We show that a unique match is obtained as the outcome of each sd-Nash equilibrium. Furthermore, individual-rationality with respect to the true preferences is a necessary and sufficient condition for an equilibrium outcome. In the many-to-one framework, the outcome of each equilibrium in which firms behave truthfully is stable for the true preferences. In the many-to-many framework, we identify an equilibrium in which firms behave truthfully and yet the equilibrium outcome is not stable for the true preferences. However, each stable match for the true preferences can be achieved as the outcome of such equilibrium.     

Rotational analysis of some bands of C1 Σ u + -X1 Σ g + system of P2 molecule involving lowν′,ν″ values

Ten ultraviolet bands of the C¹ Σ _u ⁺ -X¹ Σ _g ⁺ system of P₂ involving lowv′ andv″ values have been photographed at dispersion of 0·38 and 0·56 Å/mm. and analysed for their rotational structure. While four of these bands were analysed earlier, six of them,viz., 0–10, 1–12, 2–7, 2–14, 4–8 and 6–9 have been analysed for the first time during the present studies. The rotational constants, B _v S with lowv″ quantum numbers are obtained from which value of B _θ ^″ has been derived. The value of B _θ ^″ is found to be in agreement with the value obtained by Douglas and Rao from their study of A¹ Π _g-X¹ Σ _g ⁺ bands of P₂. Earlier findings on the perturbation ofν′=2 level of the C¹ Σ _u ⁺ state have been confirmed from the analysis of the 2–7, 2–14 and 2–15 bands. Theν ₀₀ values of the bands show large deviations from the expected values.     

New class of hybrid BDF methods for the computation of numerical solutions of IVPs

A new class of hybrid BDF-like methods is presented for solving systems of ordinary differential equations (ODEs) by using the second derivative of the solution in the stage equation of class 2 + 1hybrid BDF-like methods to improve the order and stability regions of these methods. An off-step point, together with two step points, has been used in the first derivative of the solution, and the stability domains of the new methods have been obtained by showing that these methods are A-stable for order p, p =?3,4,5,6,7and A(α)-stable for order p, 8 ≤ p ≤?14. The numerical results are also given for four test problems by using variable and fixed step-size implementations.     

Jacobi method for symmetric 4 × 4 matrices converges for every cyclic pivot strategy

The paper studies the global convergence of the Jacobi method for symmetric matrices of size 4. We prove global convergence for all 720 cyclic pivot strategies. Precisely, we show that inequality S(A ^[t+3]) ≤ γ S(A ^[t]), t ≥ 1, holds with the constant γ < 1 that depends neither on the matrix A nor on the pivot strategy. Here, A ^[t] stands for the matrix obtained from A after t full cycles of the Jacobi method and S(A) is the off-diagonal norm of A. We show why three consecutive cycles have to be considered. The result has a direct application on the J-Jacobi method.     

Global Asymptotics of Orthogonal Polynomials Associated with a Generalized Freud Weight

In this paper,the authors consider the asymptotic behavior of the monic polynomials orthogonal with respect to the weight function w(x) = |x|~(2α)e~(-(x~4+tx~2)),x ∈ R,where α is a constant larger than -1/2 and t is any real number. They consider this problem in three separate cases:(i) c -2,(ii) c =-2,and(iii) c -2,where c := t N~(-1/2) is a constant,N = n + α and n is the degree of the polynomial. In the first two cases,the support of the associated equilibrium measure μ_t is a single interval,whereas in the third case the support of μ_t consists of two intervals. In each case,globally uniform asymptotic expansions are obtained in several regions. These regions together cover the whole complex plane. The approach is based on a modified version of the steepest descent method for Riemann-Hilbert problems introduced by Deift and Zhou(1993).     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Vectorial Ekeland variational principle for systems of equilibrium problems and its applications

For a family of vector-valued bifunctions,we introduce the notion of sequentially lower monotonity,which is strictly weaker than the lower semi-continuity of the second variables of the bifunctions.Then,we give a general version of vectorial Ekeland variational principle(briefly,denoted by EVP) for a system of equilibrium problems,where the sequentially lower monotone objective bifunction family is defined on products of sequentially lower complete spaces(concerning sequentially lower complete spaces,see Zhu et al(2013)),and taking values in a quasi-ordered locally convex space.Besides,the perturbation consists of a subset of the ordering cone and a family {p_i}_(i∈I) of negative functions satisfying for each i∈I,p_i(x_i,y_i) = 0 if and only if x_i=y_i.From the general version,we can deduce several particular equilibrium versions of EVP,which can be applied to show the existence of solutions for countable systems of equilibrium problems.In particular,we obtain a general existence result of solutions for countable systems of equilibrium problems in the setting of sequentially lower complete spaces.By weakening the compactness of domains and the lower semi-continuity of objective bifunctions,we extend and improve some known existence results of solutions for countable system of equilibrium problems in the setting of complete metric spaces(or Fréchet spaces).When the domains are non-compact,by using the theory of angelic spaces(see Floret(1980)),we generalize some existence results on solutions for countable systems of equilibrium problems by extending the framework from reflexive Banach spaces to the strong duals of weakly compactly generated spaces.     

On the number of edges in a uniform hypergraph with a range of permitted intersections

The paper studies the quantity p(n, k, t ₁, t ₂) equal to the maximum number of edges in a k-uniform hypergraph with the property that the size of the intersection of any two edges lies in the interval [t ₁, t ₂]. Previously known upper and lower bounds are given. New bounds for p(n, k, t ₁, t ₂) are obtained, and the relationship between these bounds and known estimates is studied. For some parameter values, the exact values of p(n, k, t ₁, t ₂) are explicitly calculated.     

On Stability of Thomson’s Vortex <Emphasis Type="Italic">N</Emphasis>-gon in the Geostrophic Model of the Point Bessel Vortices

A stability analysis of the stationary rotation of a system of N identical point Bessel vortices lying uniformly on a circle of radius R is presented. The vortices have identical intensity Γ and length scale γ^?1 > 0. The stability of the stationary motion is interpreted as equilibrium stability of a reduced system. The quadratic part of the Hamiltonian and eigenvalues of the linearization matrix are studied. The cases for N = 2,..., 6 are studied sequentially. The case of odd N = 2?+1 ≥ 7 vortices and the case of even N = 2_n ≥ 8 vortices are considered separately. It is shown that the (2? + 1)-gon is exponentially unstable for 0 < γR<R_*(N). However, this (2? + 1)-gon is stable for γR ≥ R_*(N) in the case of the linearized problem (the eigenvalues of the linearization matrix lie on the imaginary axis). The even N = 2n ≥ 8 vortex 2n-gon is exponentially unstable for R > 0.     

Adjoining batch Markov arrival processes of a Markov chain

A batch Markov arrival process (BMAP) X* = (N, J) is a 2-dimensional Markov process with two components, one is the counting process N and the other one is the phase process J. It is proved that the phase process is a time-homogeneous Markov chain with a finite state-space, or for short, Markov chain. In this paper, a new and inverse problem is proposed firstly: given a Markov chain J, can we deploy a process N such that the 2-dimensional process X* = (N, J) is a BMAP? The process X* = (N, J) is said to be an adjoining BMAP for the Markov chain J. For a given Markov chain the adjoining processes exist and they are not unique. Two kinds of adjoining BMAPs have been constructed. One is the BMAPs with fixed constant batches, the other one is the BMAPs with independent and identically distributed (i.i.d) random batches. The method we used in this paper is not the usual matrix-analytic method of studying BMAP, it is a path-analytic method. We constructed directly sample paths of adjoining BMAPs. The expressions of characteristic (D _k , k = 0, 1, 2 · · ·) and transition probabilities of the adjoining BMAP are obtained by the density matrix Q of the given Markov chain J. Moreover, we obtained two frontal Theorems. We present these expressions in the first time.     

Lebesgue constants of the Walsh system and Banach limits

We study the properties of the Lebesgue constants of the Walsh system L_n(W), n ∈ N, and apply the results to the theory of Banach limits. We show that the sequence \(\left\{ {\frac{{{L_n}\left( W \right)}}{{{{\log }_2}n}},n \geqslant 2} \right\}\) does not belong to the space of almost convergent sequences ac, which reveals their extremely irregular behavior. Several results of the opposite nature are obtained for some special means of these constants.     

The Generalized <Emphasis Type="Italic">M/G/k</Emphasis> Blocking System with Heterogeneous Servers

This paper studies the equilibrium behaviour of the generalized M/G/k blocking system with heterogeneous servers. Such a service system has k servers, each with a (possibly) different service time distribution, whose customers arrive in accordance with a Poisson process. They are served, unless all the servers are occupied. In this case they leave and they do not return later (i.e. they are ‘blocked’). Whenever there are n (n = 0, 1, 2,..., k) servers occupied, each arriving customer balks with probability 1 - f _{n +1}(f _{k +1} = 0) and each server works at a rate g _n . Among other things, a generalization of the Erlang B-formula is given and also it is shown that the equilibrium departure process from the system is Poisson.     

Some irreducibility and indecomposability results for truncated binomial polynomials of small degree

In this paper, we show that the truncated binomial polynomials defined by \(P_{n,k}(x)={\sum }_{j=0}^{k} {n \choose j} x^{j}\) are irreducible for each k≤6 and every n≥k+2. Under the same assumption n≥k+2, we also show that the polynomial P _n,k cannot be expressed as a composition P _n,k (x) = g(h(x)) with \(g \in \mathbb {Q}[x]\) of degree at least 2 and a quadratic polynomial \(h \in \mathbb {Q}[x]\). Finally, we show that for k≥2 and m,n≥k+1 the roots of the polynomial P _m,k cannot be obtained from the roots of P _n,k , where m≠n, by a linear map.     

Asymptotics and Arithmetical Properties of Complexity for Circulant Graphs

Abstract—We study analytical and arithmetical properties of the complexity function for infinite families of circulant C _n (s₁, s_2,…, s _k ) C_2n(s₁, s_2,…, s _k , n). Exact analytical formulas for the complexity functions of these families are derived, and their asymptotics are found. As a consequence, we show that the thermodynamic limit of these families of graphs coincides with the small Mahler measure of the accompanying Laurent polynomials.     

On the Extremal Zagreb Indices of Graphs with Cut Edges

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M ₁- and M ₂-value are obtained, respectively, and uniquely, at K _n ^k (resp. P _n ^k ), where K _n ^k is a graph obtained by joining k independent vertices to one vertex of K _n?k and P _n ^k is a graph obtained by connecting a pendent path P _k+1 to one vertex of C _n?k.     

Under-recurrence in the Khintchine recurrence theorem

The Khintchine recurrence theorem asserts that in a measure preserving system, for every set A and ε > 0, we have μ(A ∩ T^?nA) ≥ μ(A)² ? ε for infinitely many n ∈ N. We show that there are systems having underrecurrent sets A, in the sense that the inequality μ(A ∩ T^?nA) < μ(A)² holds for every n ∈ N. In particular, all ergodic systems of positive entropy have under-recurrent sets. On the other hand, answering a question of V. Bergelson, we show that not all mixing systems have under-recurrent sets. We also study variants of these problems where the previous strict inequality is reversed, and deduce that under-recurrence is a much more rare phenomenon than over-recurrence. Finally, we study related problems pertaining to multiple recurrence and derive some interesting combinatorial consequences.     

Lattices generated by joins of the flats in orbits under finite affine-singular symplectic group and its characteristic polynomials

Let ASG(2ν + l, ν;F _q ) be the (2ν + l)-dimensional affine-singular symplectic space over the finite field F _q and ASp_2ν+l,ν (F _q ) be the affine-singular symplectic group of degree 2ν + l over F _q . Let O be any orbit of flats under ASp_2ν+l,ν (F _q ). Denote by L ^J the set of all flats which are joins of flats in O such that O ? L ^J and assume the join of the empty set of flats in ASG(2ν + l, ν;F _q ) is ?. Ordering L ^J by ordinary or reverse inclusion, then two lattices are obtained. This paper firstly studies the inclusion relations between different lattices, then determines a characterization of flats contained in a given lattice L ^J , when the lattices form geometric lattice, lastly gives the characteristic polynomial of L ^J .     

Certain pairs of irreducible characters of the groups <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The investigation of the pairs of irreducible characters of the symmetric group S _n that have the same set of roots in one of the sets A _n and S _n ? A _n is continued. All such pairs of irreducible characters of the group S _n are found in the case when the least of the main diagonal’s lengths of the Young diagrams corresponding to these characters does not exceed 2. Some arguments are obtained for the conjecture that alternating groups A _n have no pairs of semiproportional irreducible characters.     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).