Cyclic Tableaux and Symmetric Functions

We introduce the notion of cyclic tableaux and develop involutions for Waring's formulas expressing the power sum symmetric function p_n in terms of the elementary symmetric function e_n and the homogeneous symmetric function h_n. The coefficients appearing in Waring's formulas are shown to be a cyclic analog of the multinomial coefficients, a fact that seems to have been neglected before. Our involutions also spell out the duality between these two forms of Waring's formulas, which turns out to be exactly the “duality between sets and multisets.” We also present an involution for permutations in cycle notation, leading to probably the simplest combinatorial interpretation of the Möbius function of the partition lattice and a purely combinatorial treatment of the fundamental theorem on symmetric functions. This paper is motivated by Chebyshev polynomials in connection with Waring's formula in two variables.     

Thed-step conjecture for polyhedra of dimensiond<6

Two functions Δ and Δ _b , of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Δ(d, n) is the maximum diameter of convex polyhedra of dimensiond withn faces of dimensiond−1; similarly, Δ _b (d,n) is the maximum diameter of bounded polyhedra of dimensiond withn faces of dimensiond−1. The diameter of a polyhedronP is the smallest integerl such that any two vertices ofP can be joined by a path ofl or fewer edges ofP. It is shown that the boundedd-step conjecture, i.e. Δ _b (d,2d)=d, is true ford≤5. It is also shown that the generald-step conjecture, i.e. Δ(d, 2d)≤d, of significance in linear programming, is false ford≥4. A number of other specific values and bounds for Δ and Δ _b are presented. This revised version was published online in November 2006 with corrections to the Cover Date.     

Some Results for Decomposition Numbers for the Hecke Algebra of Type A with q = −1

Let ? = ?_{?, ?1}(𝔖 _n ) be the Hecke algebra of the symmetric group 𝔖 _n . For partitions λ and ν with ν 2 ? regular, define the Specht module S(λ) and the irreducible module D(ν). Define d _λν = [S(λ): D(ν)] to be the composition multiplicity of D(ν) in S(λ). In this paper we compute the decomposition numbers d _λν for all partitions of the form λ = (a, c, 1 ^b ) and ν 2 ? regular.     

New Combinatorial Descriptions of the Triangulations of Cyclic Polytopes and the Second Higher Stasheff–Tamari Posets

This paper is concerned with the d-dimensional cyclic polytope with n vertices, C(n,d), and the set of its triangulations, S(n,d). We show that there is a bijection between S(n,d) and certain partitions of the set of increasing d-tuples on the integers 1 to n–1. We give a combinatorial characterization of the second higher Stasheff–Tamari poset, which is a partial ordering of S(n,d), and we determine its 2-dimension. There is a well-known representation of triangulations of an n-gon by right bracket vectors. We generalize this to cyclic polytopes of higher dimensions.     

On the number of nonzero digits of the partition function

Let p(n) be the function that counts the number of partitions of n. Let b ≥ 2 be a fixed positive integer. In this paper, we show that for almost all n the sum of the digits of p(n) in base b is at least log n/(7log log n). Our proof uses the first term of Rademacher’s formula for p(n).     

Arithmetic of the 13-regular partition function modulo 3

Let b ₁₃(n) denote the number of 13-regular partitions of n. We study in this paper the behavior of b ₁₃(n) modulo 3 where n≡1 (mod 3). In particular, we identify an infinite family of arithmetic progressions modulo arbitrary powers of 3 such that b ₁₃(n)≡0 (mod 3).     

An Asymptotic Isoperimetric Inequality

For a finite metric space V with a metric , let V ⁿ be the metric space in which the distance between (a ₁ , . . ., a _n ) and (b ₁ , . . ., b _n ) is the sum . We obtain an asymptotic formula for the logarithm of the maximum possible number of points in V ⁿ of distance at least d from a set of half the points of V ⁿ , when n tends to infinity and d satisfies . Submitted: September 1997, Final version: November 1997     

Congruences for ?-regular partition functions modulo 3

Let b _ℓ (n) denote the number of ℓ-regular partitions of n. Recently Andrews, Hirschhorn, and Sellers proved that b ₄(n) satisfies two infinite families of congruences modulo 3, and Webb established an analogous result for b ₁₃(n). In this paper we prove similar families of congruences for b _ℓ (n) for other values of ℓ.     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.     

Hook Lengths and 3-Cores

Recently, the first author generalized a formula of Nekrasov and Okounkov which gives a combinatorial formula, in terms of hook lengths of partitions, for the coefficients of certain power series. In the course of this investigation, he conjectured that a(n) = 0 if and only if b(n) = 0, where integers a(n) and b(n) are defined by

Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary

We consider the manifolds H _n(φ) formed by all possible linear combinations of n functions from the set {φ(A⋅+b)}, where x→Ax+b is arbitrary affine mapping in the space ℝ^d. For example, neural networks and radial basis functions are the manifolds of type H _n(φ). We obtain estimates for pseudo-dimension of the manifold H _n(φ) for wide collection of the generator function φ. The estimates have the order O(d ² n) in degree scale, that is the order is proportional to number of parameters of the manifold H _n(φ). Moreover the estimates for ɛ-entropy of the manifold H _n(φ) are obtained. Mathematics subject classifications (2000) 41A46, 41A50, 42A61, 42C10 V. Maiorov: Supported by the Center for Absorption in Science, Ministry of Immigrant Absorption, State of Israel.     

Orthonormal Sequences in L 2(R d ) and Time Frequency Localization

We prove that there does not exist an orthonormal basis {b _n } for L ²(R) such that the sequences {μ(b _n )}, {m([^(b_n)])}\{\mu(\widehat{b_{n}})\} , and {D(b_n)D([^(b_n)])}\{\Delta(b_{n})\Delta(\widehat{b_{n}})\} are bounded. A higher dimensional version of this result that involves generalized dispersions is also obtained. The main tool is a time-frequency localization inequality for orthonormal sequences in L ²(R ^d ). On the other hand, for d>1 we construct a basis {b _n } for L ²(R ^d ) such that the sequences {μ(b _n )}, {m([^(b_n)])}\{\mu(\widehat{b_{n}})\} , and {D(b_n)D([^(b_n)])}\{\Delta(b_{n})\Delta(\widehat{b_{n}})\} are bounded.     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

Counting partitions on the abacus

In 2003, Maróti showed that one could use the machinery of ℓ-cores and ℓ-quotients of partitions to establish lower bounds for p(n), the number of partitions of n. In this paper we explore these ideas in the case ℓ=2, using them to give a largely combinatorial proof of an effective upper bound on p(n), and to prove asymptotic formulae for the number of self-conjugate partitions, and the number of partitions with distinct parts. In a further application we give a combinatorial proof of an identity originally due to Gauss. Dedicated to the memory of Dr. Manfred Schocker (1970–2006)     

A New Proof of the Mullineux Conjecture

Let S _d denote the symmetric group on d letters. In 1979 Mullineux conjectured a combinatorial algorithm for calculating the effect of tensoring with an irreducible S _d-module with the one dimensional sign module when the ground field has positive characteristic. Kleshchev proved the Mullineux conjecture in 1996. In the present article we provide a new proof of the Mullineux conjecture which is entirely independent of Kleshchev's approach. Applying the representation theory of the supergroup GL(m | n) and the supergroup analogue of Schur-Weyl Duality it becomes straightforward to calculate the combinatorial effect of tensoring with the sign representation and, hence, to verify Mullineux's conjecture. Similar techniques also allow us to classify the irreducible polynomial representations of GL(m | n) of degree d for arbitrary m, n, and d.     

Infinitely many pairs of cospectral integral regular graphs

A graph G is called integral if all the eigenvalues of the adjacency matrix A(G) of G are integers. In this paper, the graphs G ₄(a, b) and G ₅(a, b) with 2a+6b vertices are defined. We give their characteristic polynomials from matrix theory and prove that the (n+2)-regular graphs G ₄(n, n+2) and G ₅(n, n+2) are a pair of non-isomorphic connected cospectral integral regular graphs for any positive integer n.     

The Combinatorics of a Class of Representation Functions

In the study of the irreducible representations of the unitary groupU(n), one encounters a class of polynomials defined onn²indeterminatesz_ij, 1i, jn, which may be arranged into ann×nmatrix arrayZ=(z_ij). These polynomials are indexed by double Gelfand patterns, or equivalently, by pairs of column strict Young tableaux of the same shape. Using the double labeling property, one may define a square matrixD(Z), whose elements are the double-indexed polynomials. These matrices possess the remarkable “group multiplication property”D(XY)=D(X) D(Y) for arbitrary matricesXandY, even though these matrices may be singular. ForZ=UU(n), these matrices give irreducible unitary representations ofU(n). These results are known, but not always fully proved from the extensive physics literature on representation of the unitary groups, where they are often formulated in terms of the boson calculus, and the multiplication property is unrecognized. The generality of the multiplication property is the key to understanding group representation theory from the purview of combinatorics. The combinatorial structure of the general polynomials is expected to be intricate, and in this paper, we take the first step to explore the combinatorial aspects of a special class which can be defined in terms of the set of integral matrices with given row and column sums. These special polynomials are denoted byL_{α, β}(Z), whereαandβare integral vectors representing the row sums and column sums of a class of integral matrices. We present a combinatorial interpretation of the multiplicative properties of these polynomials. We also point out the connections with MacMahon's Master Theorem and Schwinger's inner product formula, which is essentially equivalent to MacMahon's Master Theorem. Finally, we give a formula for the double Pfaffian, which is crucial in the studies of the generating function of the 3n−jcoefficients in angular momentum theory. We also review the background of the general polynomials and give some of their properties.     

A method of constructing Krall's polynomials

We propose a method of constructing orthogonal polynomials P_n(x) (Krall's polynomials) that are eigenfunctions of higher-order differential operators. Using this method we show that recurrence coefficients of Krall's polynomials P_n(x) are rational functions of n. Let P_n^(a,b;M)(x) be polynomials obtained from the Jacobi polynomials P_n^(a,b)(x) by the following procedure. We add an arbitrary concentrated mass M at the endpoint of the orthogonality interval with respect to the weight function of the ordinary Jacobi polynomials. We find necessary conditions for the parameters a,b in order for the polynomials P_n^(a,b;M)(x) to obey a higher-order differential equation. The main result of the paper is the following. Let a be a positive integer and b⩾−1/2 an arbitrary real parameter. Then the polynomials P_n^(a,b;M)(x) are Krall's polynomials satisfying a differential equation of order 2a+4.     

Cleaning Random d-Regular Graphs with Brooms

A model for cleaning a graph with brushes was recently introduced. Let α = (v ₁, v ₂, . . . , v _n ) be a permutation of the vertices of G; for each vertex v _i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N^-(v_i)={j: v_j v_i ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let b_a(G)=?_i=1ⁿ max{|N⁺(v_i)|-|N^-(v_i)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max _α b _α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.     

Asymptotic Enumeration of Convex Polygons

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice ^dtaking at least one step in every dimension. A polygon on ^dis said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number ofd-dimensional convex polygonsp_{n, d}of length 2nwithd(n)→∞ is asymptoticallywherer=r(n, d) is the unique solution ofr coth r=2n/d−1andb(r)=d(r coth r−r²/sinh² r). The convergence is uniform over alld?ω(n) for any functionω(n)→∞. Whendis constant the exponential is replaced with (1−d⁻¹)^2d. These results are proved by asymptotically enumerating a larger class of combinatorial objects calledconvex proto-polygonsby the saddle-point method and then finding the asymptotic probability a randomly chosen convex proto-polygon is a convex polygon.