Using Noonan–Zeilberger Functional Equations to enumerate (in polynomial time!) generalized Wilf classes

One of the most challenging problems in enumerative combinatorics is to count Wilf classes, where you are given a pattern, or set of patterns, and you are asked to find a “formula”, or at least an efficient algorithm, that inputs a positive integer n and outputs the number of permutations avoiding that pattern. In 1996, John Noonan and Doron Zeilberger initiated the counting of permutations that have a prescribed, r, say, occurrences of a given pattern. They gave an ingenious method to generate functional equations, alas, with an unbounded number of “catalytic variables”, but then described a clever way, using multivariable calculus, on how to get enumeration schemes. Alas, their method becomes very complicated for r larger than 1. In the present article we describe a far simpler way to squeeze the necessary information, in polynomial time, for increasing patterns of any length and for any number of occurrences r.     

Spanning forests and the golden ratio

For a graph G, let f_ij be the number of spanning rooted forests in which vertex j belongs to a tree rooted at i. In this paper, we show that for a path, the f_ij's can be expressed as the products of Fibonacci numbers; for a cycle, they are products of Fibonacci and Lucas numbers. The doubly stochastic graph matrix is the matrix F=(f_ij)_n×n/f, where f is the total number of spanning rooted forests of G and n is the number of vertices in G. F provides a proximity measure for graph vertices. By the matrix forest theorem, F^-1=I+L, where L is the Laplacian matrix of G. We show that for the paths and the so-called T-caterpillars, some diagonal entries of F (which provide a measure of the self-connectivity of vertices) converge to φ^-1 or to 1-φ^-1, where φ is the golden ratio, as the number of vertices goes to infinity. Thereby, in the asymptotic, the corresponding vertices can be metaphorically considered as “golden introverts” and “golden extroverts,” respectively. This metaphor is reinforced by a Markov chain interpretation of the doubly stochastic graph matrix, according to which F equals the overall transition matrix of a random walk with a random number of steps on G.     

A new bound for neighbor-connectivity of abelian Cayley graphs

For the notion of neighbor-connectivity in graphs, whenever a vertex is “subverted” the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. The main result of this paper is a sharpening of the bound for abelian Cayley graphs. In particular, we show by constructing an effective subversion strategy for such graphs, that neighbor-connectivity is bounded above by ⌈δ/2⌉+2. Using a result of Watkins the new bound can be recast in terms of κ to get neighbor-connectivity bounded above by ⌈3κ/4⌉+2 for abelian Cayley graphs.     

A new rating system for duplicate bridge

We propose a new way to rate individual duplicate bridge players, which we believe is superior to the masterpoint system currently used by the American Contract Bridge League. This method measures only a player’s current skill level, and not how long or how frequently he has played. It is based on simple ideas from the theory of statistics and from linear algebra, and should be easy to implement.One particular issue which can occur within any system proposing to rate individual players using results earned by partnerships is what we call the “nonuniqueness problem”. This refers to the occasional inability for data to distinguish who is the “good player” and who is the “bad player” within particular partnerships. We prove that under our system this problem disappears if either (a) a certain “partnership graph” has no bipartite components, or if (b) every player is required to participate in at least one individual game.Finally, we present some data from a bridge club in Reno, NV. They show that even if (a) and (b) do not hold, our system will provide (unique) ratings for most players.     

Remarks on the minus (signed) total domination in graphs

A function f:V(G)→{+1,0,-1} defined on the vertices of a graph G is a minus total dominating function if the sum of its function values over any open neighborhood is at least 1. The minus total domination number of G is the minimum weight of a minus total dominating function on G. By simply changing “{+1,0,-1}” in the above definition to “{+1,-1}”, we can define the signed total dominating function and the signed total domination number of G. In this paper we present a sharp lower bound on the signed total domination number for a k-partite graph, which results in a short proof of a result due to Kang et al. on the minus total domination number for a k-partite graph. We also give sharp lower bounds on and for triangle-free graphs and characterize the extremal graphs achieving these bounds.     

The Topological Tverberg Theorem and winding numbers

The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d?1, and if q is a prime power, but not yet in general.)The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a “Winding Number Conjecture” that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to R^d. “Many Tverberg partitions” arise if and only if there are “many q-winding partitions.”The d=2 case of the Winding Number Conjecture is a problem about drawings of the complete graphs K_3q-2 in the plane. We investigate graphs that are minimal with respect to the winding number condition.     

Generating binary trees with uniform probability

A binary tree is characterized as a sequence of graftings. This sequence is used to construct a Markov chain useful for generating trees with uniform probability. A code for the Markov chain gives a characteristic binary string for the trees. The main result is the calculation of the transition probabilities of the Markov chain. Some applications are pointed out.     

Lifted generalized permutahedra and composition polynomials

Generalized permutahedra are the polytopes obtained from the permutahedron by changing the edge lengths while preserving the edge directions, possibly identifying vertices along the way. We introduce a “lifting” construction for these polytopes, which turns an n  -dimensional generalized permutahedron into an (n+1)$(n+1)$-dimensional one. We prove that this construction gives rise to Stasheff ?s multiplihedron from homotopy theory, and to the more general “nestomultiplihedra”, answering two questions of Devadoss and Forcey.     

On the stability of the Serrin problem

We investigate stability issues concerning the radial symmetry of solutions to Serrin's overdetermined problems. In particular, we show that, if u is a solution to Δu=n in a smooth domain Ω⊂Rn, u=0 on ∂Ω and |Du| is “close” to 1 on ∂Ω, then Ω is “close” to the union of a certain number of disjoint unitary balls.     

Stability of wavelet-like expansions under chromatic aberration

We prove that wavelet and wavelet-like expansions of functions are Lp-stable under small (but otherwise arbitrary and independent) errors in translation and dilation of the constituent reproducing kernels. These perturbations are frequency-dependent, which is why we call them “chromatic aberration.” We show that, if these errors have sizes no bigger than η, then the Lp distance between the “true” and “perturbed” output functions is bounded by a constant times ητ‖fp_‖, where τ is a positive number depending on the family of kernels in question. We show that this result also holds in Lp(w) if w is a Muckenhoupt Ap weight.     

Universal G-spaces for proper actions of locally compact groups

We establish the existence of universal G-spaces for proper actions of locally compact groups on Tychonoff spaces. A typical result sounds as follows: for each infinite cardinal number τ every locally compact, non-compact, σ-compact group G of weight w(G)?τ, can act properly on Rτ?{0} such that Rτ?{0} contains a G-homeomorphic copy of every Tychonoff proper G-space of weight ?τ. The metric cones Cone(G/H) with H⊂G a compact subgroup such that G/H is a manifold, are the main building blocks in our approach. As a byproduct we prove that the cardinality of the set of all conjugacy classes of such subgroups H⊂G does not exceed the weight of G.     

A direct bijection for the Harer-Zagier formula

We give a combinatorial proof of Harer and Zagier's formula for the disjoint cycle distribution of a long cycle multiplied by an involution with no fixed points, in the symmetric group on a set of even cardinality. The main result of this paper is a direct bijection of a set B_p,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of B_p,k are of the form (μ,π), where μ is a pairing on {1,…,2p}, π is a partition into k blocks of the same set, and a certain relation holds between μ and π. (The set partitions π that can appear in B_p,k are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for B_p,k identifies it with a set of objects of the form (ρ,t), where ρ is a pairing on a 2(p-k+1)-subset of {1,…,2p} (a “partial pairing”), and t is an ordered tree with k vertices. If we specialize to the extreme case when p=k-1, then ρ is empty, and our bijection reduces to a well-known tree bijection.     

Restricted even permutations and Chebyshev polynomials

We study generating functions for the number of even (odd) permutations on n letters avoiding 132 and an arbitrary permutation τ on k letters, or containing τ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.     

Almost equal group multiplications

In a recent paper entitled “A commutative analogue of the group ring” we introduced, for each finite group (G,⋅), a commutative graded Z-algebra R_(G,⋅) which has a close connection with the cohomology of (G,⋅). The algebra R_(G,⋅) is the quotient of a polynomial algebra by a certain ideal I_(G,⋅) and it remains a fundamental open problem whether or not the group multiplication ⋅ on G can always be recovered uniquely from the ideal I_(G,⋅).Suppose now that (G,×) is another group with the same underlying set G and identity element e∈G such that I_(G,⋅)=I_(G,×). Then we show here that the multiplications ⋅ and × are at least “almost equal” in a precise sense which renders them indistinguishable in terms of most of the standard group theory constructions. In particular in many cases (for example if (G,⋅) is Abelian or simple) this implies that the two multiplications are actually equal as was claimed in the previously cited paper.     

Eisenstein series and theta functions to the septic base

We develop a theory for Eisenstein series to the septic base, which was started by S. Ramanujan in his “Lost Notebook.” We show that two types of septic Eisenstein series may be parameterized in terms of the septic theta function and the eta quotient η⁴(7τ)/η⁴(τ). This is accomplished by constructing elliptic functions which have the septic Eisenstein series as Taylor coefficients. The elliptic functions are shown to be solutions of a differential equation, and this leads to a recurrence relation for the septic Eisenstein series.     

Klarner systems and tiling boxes with polyominoes

Let T be a protoset of d-dimensional polyominoes. Which boxes (rectangular parallelepipeds) can be tiled by T? A nice result of Klarner and Göbel asserts that the answer to this question can always be given in a particularly simple form, namely, by giving a finite list of “prime” boxes. All other boxes that can be tiled can be deduced from these prime boxes. We give a new, simpler proof of this fundamental result. We also show that there is no upper bound to the number of prime boxes, even when restricting attention to singleton protosets. In the last section, we determine the set of prime rectangles for several small polyominoes.     

On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids

Given A?{a¹,…,a^m}⊂R^d whose affine hull is R^d, we study the problems of computing an approximate rounding of the convex hull of A and an approximation to the minimum-volume enclosing ellipsoid of A. In the case of centrally symmetric sets, we first establish that Khachiyan's barycentric coordinate descent (BCD) method is exactly the polar of the deepest cut ellipsoid method using two-sided symmetric cuts. This observation gives further insight into the efficient implementation of the BCD method. We then propose a variant algorithm which computes an approximate rounding of the convex hull of A, and which can also be used to compute an approximation to the minimum-volume enclosing ellipsoid of A. Our algorithm is a modification of the algorithm of Kumar and Y?ld?r?m, which combines Khachiyan's BCD method with a simple initialization scheme to achieve a slightly improved polynomial complexity result, and which returns a small “core set.” We establish that our algorithm computes an approximate solution to the dual optimization formulation of the minimum-volume enclosing ellipsoid problem that satisfies a more complete set of approximate optimality conditions than either of the two previous algorithms. Furthermore, this added benefit is achieved without any increase in the improved asymptotic complexity bound of the algorithm of Kumar and Y?ld?r?m or any increase in the bound on the size of the computed core set. In addition, the “dropping idea” used in our algorithm has the potential of computing smaller core sets in practice. We also discuss several possible variants of this dropping technique.     

Finite presentation of fibre products of metabelian groups

We show that if Γ is a finitely presented metabelian group, then the “untwisted” fibre product or pull-back P associated to any short exact sequence 1→N→Γ→Q→1 is again finitely presented. In contrast, if N and Q are abelian, then the analogous “twisted” fibre-product is not finitely presented unless Γ is polycyclic. Also a number of examples are constructed, including a non-finitely presented metabelian group P with finitely generated.