Submodular partition functions

Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble number of a graph and its tree-width. Our approach is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The proof does not rely on Menger’s theorem, and thus generalises the original one. It thus provides a dual for matroid tree-width. One can also derive all known dual notions of other classical width-parameters from it.     

Instanton partition functions and M-theory

We discuss instanton partition functions in various spacetime dimensions. These partition functions capture some information about the spectrum of the supersymmetric gauge theories and their low-energy dynamics. Some of these theories can be defined microscopically only through string theory. Remarkably, they even know about the M-theory. Our conjectures include the identities between the generalization of the MacMahon formula and the character of M-theory, compactified down to 0 + 1 dimension. This article is based on the 5th Takagi Lectures that the author delivered at the University of Tokyo on October 4 and 5, 2008.     

Congruences for partition functions related to mock theta functions

The Ramanujan Journal - Partitions associated with mock theta functions have received a great deal of attention in the literature. Recently, Choi and Kim derived several partition identities from...     

Simple upper bounds for partition functions

We tweak Siegel’s method to produce a rather simple proof of a new upper bound on the number of partitions of an integer into an exact number of parts. Our approach, which exploits the delightful dilogarithm function, extends easily to numerous other counting functions. This work was supported by PSC/CUNY Research Awards (# 67261-00 36 and # 68327-00 37).     

Computability of width of submodular partition functions

The notion of submodular partition functions generalizes many of well-known tree decompositions of graphs. For fixed k$k$, there are polynomial-time algorithms to determine whether a graph has tree-width, branch-width, etc. at most k$k$. Contrary to these results, we show that there is no sub-exponential algorithm for determining whether the width of a given submodular partition function is at most two.     

A combinatorial proof of Andrews' partition functions related to Schur's partition theorem

We construct an involution to show equality between partition functions related to Schur's second partition theorem.

     

Estimates on binomial sums of partition functions

Let p(n) denote the partition function and define where p(0)= 1. We prove that p(n,k) is unimodal and satisfies for fixed n≥ 1 and all 1≤k≤n. This result has an interesting application: the minimal dimension of a faithful module for a k-step nilpotent Lie algebra of dimension n is bounded by p(n,k) and hence by , independently of k. So far only the bound n ^{n −1} was known. We will also prove that for n≥ 1 and . Received: 17 December 1999     

\ell -Adic properties of partition functions

Folsom, Kent, and Ono used the theory of modular forms modulo $\ell $ to establish remarkable “self-similarity” properties of the partition function and give an overarching explanation of many partition congruences. We generalize their work to analyze powers $p_r$ of the partition function as well as Andrews’s $spt$ -function. By showing that certain generating functions reside in a small space made up of reductions of modular forms, we set up a general framework for congruences for $p_r$ and $spt$ on arithmetic progressions of the form $\ell ^mn+\delta $ modulo powers of $\ell $ . Our work gives a conceptual explanation of the exceptional congruences of $p_r$ observed by Boylan, as well as striking congruences of $spt$ modulo 5, 7, and 13 recently discovered by Andrews and Garvan.     

A sufficient condition for planar partition functions

This research was supported by a Feodor Lynen fellowship.     

Asymptotic formulas for some retricted partition functions

We use Rademacher’s method to obtain asymptotic expressions for some restricted partition functions. For fixed positive integers m > 1 and l, we consider the number p _m (n) of partitions of n into summands not divisible by m, and the number p _m ^l (n) of partitons of n with the further restriction that any integer occurs at most l times as a summand. 2000 Mathematics Subject Classification Primary—11P82; Secondary—11P83     

Congruences for t-core partition functions

Let t?2$t?2$ be an integer and p?5$p?5$ be a prime. We prove a conjecture on congruences for 2^t$2^t$-core partition functions. We also find many new congruences for p  -core partition functions when 5?p?47$5?p?47$.     

On the parity of generalized partition functions II

Let A = {а 1 < a 2 < ...} be a set of positive integers and A(x) its counting function. Let us denote the number of partitions of n with parts in A by p( A , n). Improving on two preceding papers jointly written with I.Z. Ruzsa and A. Sárközy (J. Number Theory, 1998) and with A. Sárközy (Millennial Conference on Number Theory, May 2000, Urbana, Illinois, U.S.A.), it is shown that there exists a set A satisfying A(x) > c xlog log x/ (log x) 1/3 , c<0, such that, for n large enough, p( A ; n) isalways even.     

Generating functions for vector partition functions and a basic recurrence relation

ABSTRACT

We define a generalized vector partition function and derive an identity for the generating series of such functions associated with solutions to basic recurrence relations of combinatorial analysis. As a consequence we obtain the generating function of the number of generalized lattice paths and a new version of the Chaundy-Bullard identity for the vector partition function.     

An elementary derivation of the asymptotics of partition functions

Let S_a,b = {an+b:n ≥ 0 } where n is an integer. Let P_a,b(n) denote the number of partitions of n into elements of S_a,b. In particular, we have the generating function,

Uniform partition extensions,a generating functions perspective

In this paper, a bivariate generating function CF(x, y) =f(x)-yf(xy)1-yis investigated, where f(x)= n 0fnxnis a generating function satisfying the functional equation f(x) = 1 + r j=1 m i=j-1aij xif(x)j.In particular, we study lattice paths in which their end points are on the line y = 1. Rooted lattice paths are defined. It is proved that the function CF(x, y) is a generating function defined on some rooted lattice paths with end point on y = 1. So, by a simple and unified method, from the view of lattice paths, we obtain two combinatorial interpretations of this bivariate function and derive two uniform partitions on these rooted lattice paths.     

Periodicities of partition functions and stirling numbers modulo p

If p(n, k) is the number of partitions of n into parts ≤k, then the sequence {p(k, k), p(k + 1, k),…} is periodic modulo a prime p. We find the minimum period Q = Q(k, p) of this sequence. More generally, we find the minimum period, modulo p, of {p(n; T)}_{n ≥ 0}, the number of partitions of n whose parts all lie in a fixed finite set T of positive integers. We find the minimum period, modulo p, of {S(k, k), S(k + 1, k),…}, where these are the Stirling numbers of the second kind. Some related congruences are proved. The methods involve the use of cyclotomic polynomials over Z_p[x].     

Vector partition functions and index of transversally elliptic operators

This is the first of a series of papers on partition functions and the index theory of transversally elliptic operators. In this paper we only discuss algebraic and combinatorial issues related to partition functions. The applications to index theory are in [4], while in [5] and [6] we shall investigate the cohomological formulas generated by this theory.     

Sets with even partition functions and 2-adic integers

For P ? \(\mathbb{F}_2 \)[z] with _P(0) = 1 and deg(_P) ≥ 1, let \(\mathcal{A}\) = \(\mathcal{A}\)(P) (cf. [4], [5], [13]) be the unique subset of ? such that Σ _n≥0 p(\(\mathcal{A}\), n)z ⁿ ≡ P(z) (mod 2), where p(\(\mathcal{A}\), n) is the number of partitions of n with parts in \(\mathcal{A}\). Let p be an odd prime and P ? \(\mathbb{F}_2 \)[z] be some irreducible polynomial of order p, i.e., p is the smallest positive integer such that P(z) divides 1 + z ^p in \(\mathbb{F}_2 \)[z]. In this paper, we prove that if m is an odd positive integer, the elements of \(\mathcal{A}\) = \(\mathcal{A}\)(P) of the form 2 ^k m are determined by the 2-adic expansion of some root of a polynomial with integer coefficients. This extends a result of F. Ben Saïd and J.-L. Nicolas [6] to all primes p.     

Vector partition functions and generalized dahmen and micchelli spaces

This is the first of a series of papers on partition functions and the index theory of transversally elliptic operators. In this paper we only discuss algebraic and combinatorial issues related to partition functions. The applications to index theory are in [4], while in [5] and [6] we shall investigate the cohomological formulas generated by this theory. Here we introduce a space of functions on a lattice which generalizes the space of quasipolynomials satisfying the difference equations associated to cocircuits of a sequence of vectors X, introduced by Dahmen and Micchelli [8]. This space $ \mathcal{F}(X) $ contains the partition function $ {\mathcal{P}_{(X)}} $ . We prove a “localization formula” for any f in $ \mathcal{F}(X) $ , inspired by Paradan's decomposition formula [12]. In particular, this implies a simple proof that the partition function $ {\mathcal{P}_{(X)}} $ is a quasi-polynomial on the Minkowski differences $ \mathfrak{c} - B(X) $ , where c is a big cell and B(X) is the zonotope generated by the vectors in X, a result due essentially to Dahmen and Micchelli.     

On p-adic valuations of certain m colored p-ary partition functions

The Ramanujan Journal - Let $$k\in \mathbb {N}_{\ge 2}$$ and for given $$m\in \mathbb {Z}{\setminus }\{0\}$$ consider the sequence $$(S_{k,m}(n))_{n\in \mathbb {N}}$$ defined by the power series...