New enumeration formulas for alternating sign matrices and square ice partition functions

The refined enumeration of alternating sign matrices (ASMs) of given order having prescribed behavior near one or more of their boundary edges has been the subject of extensive study, starting with the Refined Alternating Sign Matrix Conjecture of Mills–Robbins–Rumsey (1983) [25], its proof by Zeilberger (1996) [31], and more recent work on doubly-refined and triply-refined enumerations by several authors. In this paper we extend the previously known results on this problem by deriving explicit enumeration formulas for the “top–left–bottom” (triply-refined) and “top–left–bottom–right” (quadruply-refined) enumerations. The latter case solves the problem of computing the full boundary correlation function for ASMs. The enumeration formulas are proved by deriving new representations, which are of independent interest, for the partition function of the square ice model with domain wall boundary conditions at the “combinatorial point” η=2π/3$\eta =2\pi /3$.     

Balinski—Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and show that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski—Tucker (B—T) Simplex Tableaus. Furthermore, we give a strong polynomial algorithm for constructing such a B—T Simplex Tableau when a solution in the relative interior of the optimal face is known. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Alternating permutations and symmetric functions

We use the theory of symmetric functions to enumerate various classes of alternating permutations w of {1,2,…,n}. These classes include the following: (1) both w and w⁻¹ are alternating, (2) w has certain special shapes, such as (m−1,m−2,…,1), under the RSK algorithm, (3) w has a specified cycle type, and (4) w has a specified number of fixed points. We also enumerate alternating permutations of a multiset. Most of our formulas are umbral expressions where after expanding the expression in powers of a variable E, Ek is interpreted as the Euler number Ek. As a small corollary, we obtain a combinatorial interpretation of the coefficients of an asymptotic expansion appearing in Ramanujan's “Lost” Notebook.     

Quasi-symmetric functions and up–down compositions

Carlitz (1973) [5] and Rawlings (2000) [13] studied two different analogues of up–down permutations for compositions with parts in {1,…,n}. Cristea and Prodinger (2008/2009) [7] studied additional analogues for compositions with unbounded parts. We show that the results of Carlitz, Rawlings, and Cristea and Prodinger on up–down compositions are special cases of four different analogues of generalized Euler numbers for compositions. That is, for any s≥2, we consider classes of compositions that can be divided into an initial set of blocks of size s followed by a block of size j where 0≤j≤s−1. We then consider the classes of such compositions where all the blocks are strictly increasing (weakly increasing) and there are strict (weak) decreases between blocks. We show that the weight generating functions of such compositions w=w₁?w_m, where the weight of w is , are always the quotients of sums of quasi-symmetric functions. Moreover, we give a direct combinatorial proof of our results via simple involutions.     

ON THE ERROR-SUM FUNCTION OF ALTERNATING LǖIROTH SERIES

The error-sum function of alternating Lǖroth series is introduced, which, to some extent, discerns the superior or not of an expansion comparing to other expansions. Some elementary properties of this function are studied. Also, the Hausdorff dimension of graph of such function is determined.     

泰勒公式在判定二元函数极限存在性中的应用

本主要探索利用Taylor公式对无穷小量的阶进行估计，从而有效地判断出二元函数极限的存在性。     

Normal coverings of finite symmetric and alternating groups

In this paper we investigate the minimum number of maximal subgroups Hi, i=1,…,k of the symmetric group Sn (or the alternating group An) such that each element in the group Sn (respectively An) lies in some conjugate of one of the Hi. We prove that this number lies between a?(n) and bn for certain constants a,b, where ?(n) is the Euler phi-function, and we show that the number depends on the arithmetical complexity of n. Moreover in the case where n is divisible by at most two primes, we obtain an upper bound of 2+?(n)/2, and we determine the exact value for Sn when n is odd and for An when n is even.     

Color degree and alternating cycles in edge-colored graphs

Let G be an edge-colored graph. An alternating cycle of G is a cycle of G in which any two consecutive edges have distinct colors. Let d^c(v), the color degree of a vertex v, be defined as the maximum number of edges incident with v that have distinct colors. In this paper, we study color degree conditions for the existence of alternating cycles of prescribed length.     

Rationalizations of choice functions

In this paper, we are interested in the connectios between the properties of binary relations and their associated choice functions. In particular, we analyze the properties of choice functions rationalized by certain irreflexive orders.     

Binary group and Chinese postman polyhedra

A new proof of the characterization of the Chinese postman polyhedra is given. In developing this proof, a theorem of Gomory about homomorphic lifting of facets for group polyhedra is generalized to subproblems. Some results for the Chinese postman problem are generalized to binary group problems. In addition, a connection is made between Fulkerson's blocking polyhedra and a blocking pair of binary group problems. A connection is also developed between minors and lifting of facets for group problems.     

Tiling by rectangles and alternating current

This paper is on tilings of polygons by rectangles. A celebrated physical interpretation of such tilings by R.L. Brooks, C.A.B. Smith, A.H. Stone and W.T. Tutte uses direct-current circuits. The new approach of this paper is an application of alternating-current circuits. The following results are obtained:

•

a necessary condition for a rectangle to be tilable by rectangles of given shapes;

•

a criterion for a rectangle to be tilable by rectangles similar to it but not all homothetic to it;

•

a criterion for a “generic” polygon to be tilable by squares.

These results generalize those of C. Freiling, R. Kenyon, M. Laczkovich, D. Rinne, and G. Szekeres.     

Bijective proofs of shifted tableau and alternating sign matrix identities

We give a bijective proof of an identity relating primed shifted gl(n)-standard tableaux to the product of a gl(n) character in the form of a Schur function and . This result generalises a number of well-known results due to Robbins and Rumsey, Chapman, Tokuyama, Okada and Macdonald. An analogous result is then obtained in the case of primed shifted sp(2n)-standard tableaux which are bijectively related to the product of a t-deformed sp(2n) character and . All results are also interpreted in terms of alternating sign matrix (ASM) identities, including a result regarding subsets of ASMs specified by conditions on certain restricted column sums.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

The alternating algorithm in a uniformly convex and uniformly smooth Banach space

Let X   be a uniformly convex and uniformly smooth Banach space. Assume that the _Mi$M_i$, i=1,…,r$i=1,\dots ,r$, are closed linear subspaces of X  , _PMi$P_{M_i}$ is the best approximation operator to the linear subspace _Mi$M_i$, and M:=_M1+?+_Mr$M:=M_1+?+M_r$. We prove that if M is closed, then the alternating algorithm given by repeated iterations of

(I−_PMr)(I−_PMr−1)?(I−_PM1)$(I-P_{M_r})(I-P_{M_{r-1}})?(I-P_{M_1})$

applied to any x∈X$x\in X$ converges to x−_PMx$x-P_{M}x$, where _PM$P_M$ is the best approximation operator to the linear subspace M  . This result, in the case r=2$r=2$, was proven in Deutsch [4].     

Two queues with alternating service and server breakdown

We consider a queueing system with two stations served by a single server in a cyclic manner. We assume that at most one customer can be served at a station when the server arrives at the station. The system is subject to service interuption that arises from server breakdown. When a server breakdown occurs, the server must be repaired before service can resume. We obtain the approximate mean delay of customers in the system.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.     

Restrictions on the structure of subgroup lattices of finite alternating and symmetric groups

Let G be a finite alternating or symmetric group. We describe an infinite class of finite lattices, none of which is isomorphic to any interval [H,G] in the subgroup lattice of G.