Restricted colored permutations and Chebyshev polynomials

Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schröder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation.     

The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.     

Uniform cyclic edge connectivity in cubic graphs

A cubic graph which is cyclicallyk-edge connected and has the further property that every edge belongs to some cyclick-edge cut is called uniformly cyclicallyk-edge connected(U(k)). We classify theU(5) graphs and show that all cyclically 5-edge connected cubic graphs can be generated from a small finite set ofU(5) graphs by a sequence of defined operations.MATHDAHCOTAGE.AC.NZ     

Schur function identities, their t-analogs, and k-Schur irreducibility

We obtain general identities for the product of two Schur functions in the case where one of the functions is indexed by a rectangular partition, and give their t-analogs using vertex operators. We study subspaces forming a filtration for the symmetric function space that lends itself to generalizing the theory of Schur functions and also provides a convenient environment for studying the Macdonald polynomials. We use our identities to prove that the vertex operators leave such subspaces invariant. We finish by showing that these operators act trivially on the k-Schur functions, thus leading to a concept of irreducibility for these functions.     

Probability set functions

A probability set function is interpretable as a probability distribution on binary sequences of fixed length. Cumulants of probability set functions enjoy particularly simple properties which make them more manageable than cumulants of general random variables. We derive some identities satisfied by cumulants of probability set functions which we believe to be new. Probability set functions may be expanded in terms of their cumulants. We derive an expansion which allows the construction of examples of probability set functions whose cumulants are arbitrary, restricted only by their absolute values. It is known that this phenomenon cannot occur for continuous probability distributions. Some particular examples of probability set functions are considered, and their cumulants are computed, leading to a conjecture on the upper bound of the values of cumulants. Moments of probability set functions determined by arithmetical conditions are computed in a final example.Dedicated to our friend, W.A. Beyer. Financial support for this work was derived from the U.S.D.O.E. Human Genome Project, through the Center for Human Genome Studies at Los Alamos National Laboratory, and also through the Center for Nonlinear Studies, Los Alamos National Laboratory, LANL report LAUR-97-323.     

NOTE – On Minimizing Symmetric Set Functions

u, v ) of nodes such that the star of v is a minimum cut separating u and v. Nagamochi and Ibaraki showed that the last two nodes of a ``max-back order' form such a pair and used this fact to develop an elegant min-cut algorithm. M. Queyranne extended this approach to minimize symmetric submodular functions. With the help of a short and simple proof, here we show that the same algorithm works for an even more general class of set functions. Received December 16, 1998     

Minimal cut-generating functions are nearly extreme

We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory–Johnson setting as well as a recent extension by Y?ld?z and Cornuéjols (Math Oper Res 41:1381–1403, 2016). We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions are “dense” in the set of continuous (strongly) minimal functions.     

Absorbent,parabolic, elliptic and quasielliptic balayages in potential theory; relationships with the Green function

In the frame of standard H-cones of functions (the cone of all excessive functions with respect to a submarkovian resolvent of kernels with reference measure on a measurable space) on a Green set we show that the cofine closure of the complement of an absorbent set in coabsorbent. We obtain different characterizations concerning the parabolicity, ellipticity and quasiellipticity in terms of the Green function. We also show that these notions are the same in the direct and the dual theory.     

Old friends revisited: the multifractal nature of some classical functions

We study some explicit functions introduced by Riemann, Jordan, Lévy, Kahane… These functions share the property of having a dense set of discontinuities. We prove that they are examples of multifractal functions.     

Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups

Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler?s exponential generating function formula for the Eulerian numbers (Shareshian and Wachs, 2010 [17]). They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics, which generalize the Shareshian–Wachs q-analog of Euler?s formula, formulas of Foata and Han, and a formula of Chow and Gessel.     

On several classes of sets II

Summary In this paper several classes of sets are stuided. It is shown that these classes are incomparable under the relation inclusion. If the setA is in one of our classes we examine whether it must follow thatA\K is in the same class, forK a finite or countable set. We also discuss which functions preserve the various classes under consideration.The research on this paper was supported by the Foundation for Scientific Work of the Republic of Bosnia and HerzegovinaDedicated to the memory of Alexander Ostrowski on the occasion of the 100th anniversary of his birth     

On weighted multiway cuts in trees

A min—max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. We describe a dynamic programming type algorithm for this more general problem from biology and show that our min—max theorem does not apply to it.Corresponding author.Research of the author was supported by the A. v. Humboldt-Stiftung and the U.S. Office of Naval Research under the contract N-0014-91-J-1385.     

On a combinatorial property of choice functions of finite sets

We consider choice functions k[X]→X, where X is a finite set and k[X] denotes the set of all k-subsets of X. We define a property of domination for such maps generalizing the classical case k=2 (tournaments) and prove the existence of a dominating element generalizing the existence of a 2-root (king) in the classical case.     

On a class of extremal solutions of a moment problem for rational matrix-valued functions in the nondegenerate case II

The main theme of this paper is the discussion of a family of extremal solutions of a finite moment problem for rational matrix functions in the nondegenerate case. We will point out that each member of this family is extremal in several directions. Thereby, the investigations below continue the studies in Fritzsche et al. (in press) [1]. In doing so, an application of the theory of orthogonal rational matrix functions with respect to a nonnegative Hermitian matrix Borel measure on the unit circle is used to get some insights into the structure of the extremal solutions in question. In particular, we explain characterizations of these solutions in the whole solution set in terms of orthogonal rational matrix functions. We will also show that the associated Riesz-Herglotz transform of such a particular solution admits specific representations, where orthogonal rational matrix functions are involved.     

Eulerian quasisymmetric functions

We introduce a family of quasisymmetric functions called Eulerian quasisymmetric functions, which specialize to enumerators for the joint distribution of the permutation statistics, major index and excedance number on permutations of fixed cycle type. This family is analogous to a family of quasisymmetric functions that Gessel and Reutenauer used to study the joint distribution of major index and descent number on permutations of fixed cycle type. Our central result is a formula for the generating function for the Eulerian quasisymmetric functions, which specializes to a new and surprising q-analog of a classical formula of Euler for the exponential generating function of the Eulerian polynomials. This q-analog computes the joint distribution of excedance number and major index, the only of the four important Euler-Mahonian distributions that had not yet been computed. Our study of the Eulerian quasisymmetric functions also yields results that include the descent statistic and refine results of Gessel and Reutenauer. We also obtain q-analogs, (q,p)-analogs and quasisymmetric function analogs of classical results on the symmetry and unimodality of the Eulerian polynomials. Our Eulerian quasisymmetric functions refine symmetric functions that have occurred in various representation theoretic and enumerative contexts including MacMahon's study of multiset derangements, work of Procesi and Stanley on toric varieties of Coxeter complexes, Stanley's work on chromatic symmetric functions, and the work of the authors on the homology of a certain poset introduced by Björner and Welker.     

A k-tableau characterization of k-Schur functions

We study k-Schur functions characterized by k-tableaux, proving combinatorial properties such as a k-Pieri rule and a k-conjugation. This new approach relies on developing the theory of k-tableaux, and includes the introduction of a weight-permuting involution on these tableaux that generalizes the Bender-Knuth involution. This work lays the groundwork needed to prove that the set of k-Schur Littlewood-Richardson coefficients contains the 3-point Gromov-Witten invariants; structure constants for the quantum cohomology ring.     

Schur-Nevanlinna-Potapov sequences of rational matrix functions

We study particular sequences of rational matrix functions with poles outside the unit circle. These Schur-Nevanlinna-Potapov sequences are recursively constructed based on some complex numbers with norm less than one and some strictly contractive matrices. The main theme of this paper is a thorough analysis of the matrix functions belonging to the sequences in question. Essentially, such sequences are closely related to the theory of orthogonal rational matrix functions on the unit circle. As a further crosslink, we explain that the functions belonging to Schur-Nevanlinna-Potapov sequences can be used to describe the solution set of an interpolation problem of Nevanlinna-Pick type for matricial Schur functions.     

Depth-Optimized Convexity Cuts

This paper presents a general, self-contained treatment of convexity or intersection cuts. It describes two equivalent ways of generating a cut—via a convex set or a concave function—and a partial-order notion of cut strength. We then characterize the structure of the sets and functions that generate cuts that are strongest with respect to the partial order. Next, we specialize this analytical framework to the case of mixed-integer linear programming (MIP). For this case, we formulate two kinds of the deepest cut generation problem, via sets or via functions, and subsequently consider some special cases which are amenable to efficient computation. We conclude with computational tests of one of these procedures on a large set of MIPLIB problems.     

Maximal clones on uncountable sets that include all permutations

We first determine the maximal clones on a set X of infinite regular cardinality κ which contain all permutations but not all unary functions, extending a result of Heindorf’s for countably infinite X. If κ is countably infinite or weakly compact, this yields a list of all maximal clones containing the permutations, since in that case the maximal clones above the unary functions are known. We then generalize a result of Gavrilov’s to obtain on all infinite X a list of all maximal submonoids of the monoid of unary functions which contain the permutations. Received January 8, 2004; accepted in final form December 22, 2004.     

Certain classes of pluricomplex Green functions on ${\mathbb C}^n$

We consider (pluricomplex) Green functions defined on , with logarithmic poles in a finite set and with logarithmic growth at infinity. For certain sets, we describe all the corresponding Green functions. The set of these functions is large and it carries a certain algebraic structure. We also show that for some sets no such Green functions exist. Our results indicate the fact that the set of poles should have certain algebro-geometric properties in order for these Green functions to exist. Received November 24, 1998; in final form April 19, 1999 / Published online July 3, 2000