Counting labelled trees with given indegree sequence

For a labelled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij to be i→j if i<j. The indegree sequence of T can be considered as a partition λ?n−1. The enumeration of trees with a given indegree sequence arises in counting secant planes of curves in projective spaces. Recently Ethan Cotterill conjectured a formula for the number of trees on [n] with indegree sequence corresponding to a partition λ. In this paper we give two proofs of Cotterill's conjecture: one is “semi-combinatorial” based on induction, the other is a bijective proof.     

Separation of partition inequalities with terminals

Given a graph with n nodes each of them having labels equal either to 1 or 2 (a node with label 2 is called a terminal), we consider the (1,2)-survivable network design problem and more precisely, the separation problem for the partition inequalities. We show that this separation problem reduces to a sequence of submodular flow problems. Based on an algorithm developed by Fujishige and Zhang the problem is reduced to a sequence of O(n⁴) minimum cut problems.     

A bijection between 2-triangulations and pairs of non-crossing Dyck paths

A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.     

A generic approach to proving NP-hardness of partition type problems

This note presents a generic approach to proving NP-hardness of unconstrained partition type problems, namely partitioning a given set of entities into several subsets such that a certain objective function of the partition is optimized. The idea is to represent the objective function of the problem as a function of aggregate variables, whose optimum is achieved only at the points where problem Partition (if proving ordinary NP-hardness), or problem 3-Partition or Product Partition (if proving strong NP-hardness) has a solution. The approach is demonstrated on a number of discrete optimization and scheduling problems.     

A note on the partition dimension of Cartesian product graphs

Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P₁, P₂, … , P_t} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P₁), d(v, P₂), … , d(v, P_t)) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1.     

A new proof of the Ramanujan congruences for the partition function

Let p(n) denote the number of partitions of n. Recall Ramanujan’s three congruences for the partition function,

On the polynomial representation for the number of partitions with fixed length

In this paper, it is shown that the number of partitions of a nonnegative integer with parts can be described by a set of polynomials of degree in , where denotes the least common multiple of the integers and denotes the quotient of when divided by . In addition, the sets of the polynomials are obtained and shown explicitly for and .

     

Parity properties and terminal points for lattice walks with steps of equal length

A lattice walk with all steps having the same length d is called a d-walk. In this note we examine parity properties of closed d-walks in RN in relation to N and d. We also characterize real numbers d for which in R² every lattice point can be the terminal point in a d-walk starting from the origin.     

Reverse engineering of compact suffix trees and links: A novel algorithm

Invented in the 1970s, the Suffix Tree (ST) is a data structure that indexes all substrings of a text in linear space. Although more space demanding than other indexes, the ST remains likely an inspiring index because it represents substrings in a hierarchical tree structure. Along time, STs have acquired a central position in text algorithmics with myriad of algorithms and applications to for instance motif discovery, biological sequence comparison, or text compression. It is well known that different words can lead to the same suffix tree structure with different labels. Moreover, the properties of STs prevent all tree structures from being STs. Even the suffix links, which play a key role in efficient construction algorithms and many applications, are not sufficient to discriminate the suffix trees of distinct words. The question of recognising which trees can be STs has been raised and termed Reverse Engineering on STs. For the case where a tree is given with potential suffix links, a seminal work provides a linear time solution only for binary alphabets. Here, we also investigate the Reverse Engineering problem on ST with links and exhibit a novel approach and algorithm. Hopefully, this new suffix tree characterisation makes up a valuable step towards a better understanding of suffix tree combinatorics.     

A family of noetherian rings with their finite length modules under control

We investigate the category mod of finite length modules over the ring =A _k , where is a V-ring, i.e. a ring for which every simple module is injective, k a subfield of its centre and A an elementary k-algebra. Each simple module E _j gives rise to a quasiprogenerator P _j = A E _j . By a result of K. Fuller, P _j induces a category equivalence from which we deduce that mod _j mod EndP _j . As a consequence we can(1) construct for each elementary k-algebra A over a finite field k a nonartinian noetherian ring such that modA mod(2) find twisted versions of algebras of wild representation type such that itself is of finite or tame representation type (in mod)(3) describe for certain rings the minimal almost split morphisms in mod and observe that almost all of these maps are not almost split in Mod.     

A partition property of a mixed type for Pκ(λ)

Given a regular infinite cardinal κ and a cardinal λ > κ, we study fine ideals H on P_κ(λ) that satisfy the square brackets partition relation , where μ is a cardinal ≥2. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Moments about the mean of the size of a self-conjugate (s,t)-core partition

Johnson proved that if $s,t$ are coprime integers, then the $r$th moment of the size of an $(s,t)$-core is a polynomial of degree $2r$ in $t$ for fixed $s$. After that, by defining a statistic size on elements of affine Weyl group, which is preserved under the bijection between minimal coset representatives of ${\stackrel{?}{\mathfrak{S}}}_t∕{\mathfrak{S}}_t$ and $t$-cores, Thiel and Williams obtained the variance and the third moment about the mean of the size of an $(s,t)$-core. Later, Ekhad and Zeilberger stated the first six moments about the mean of the size of an $(s,t)$-core and the first nine moments about the mean of the size of an $(s,s+1)$-core using Maple. To get the moments about the mean of the size of a self-conjugate $(s,t)$-core, we proceed to follow the approach of Thiel and Williams, however, their approach does not seem to directly apply to the self-conjugate case. In this paper, following Johnson’s approach, by Ehrhart theory and Euler–Maclaurin theory, we prove that if $s,t$ are coprime integers, then the $r$th moment about the mean of the size of a self-conjugate $(s,t)$-core is a quasipolynomial of period 2 and degree $2r$ in $t$ for fixed odd $s$. Then, based on a bijection of Ford, Mai and Sze between self-conjugate $(s,t)$-cores and lattice paths in $?\frac{s}{2}?\times ?\frac{t}{2}?$ rectangle and a formula of Chen, Huang and Wang on the size of self-conjugate $(s,t)$-cores, we obtain the variance, the third moment and the fourth moment about the mean of the size of a self-conjugate $(s,t)$-core.     

A family of operators with discontinuous ranges and approximation and restoration of continuous functions

A class of operators whose construction is similar to but simpler than the construction of Landau operators is the basis for the design of a modified family of operators with discontinuous ranges. This family has good approximation properties with respect to approximation and restoration problems for continuous functions.     

A uniformly stable family of mixed hp-finite elements with continuous pressures for incompressible flow

A new family of mixed hp-finite elements is presented for thediscretization of planar Stokes flow on meshes of curvilinear,quadrilateral elements. The elements involve continuous pressuresand are shown to be stable with an inf–sup constant boundedbelow independently of the mesh-size h and the spectral orderp. The spaces have balanced approximation properties—theorders of approximation in h and p are equal for both the velocityand the pressure. This is the first example of a uniformly stablemethod with continuous pressures for spectral element discretizationof Stokes equations, valid for geometrically refined meshesand curvilinear elements.     

A family of minimax rates for density estimators in continuous time

In continuous time, rates of convergence of density estimators fluctuate with the nature of observed sample paths. In this paper, we give a family of rates reached by the kernel estimator and we show that these rates are minimax. Finally, we study applications of these results for specific classes of processes including the Gaussian ones     

A new model family for the strength distribution of fibers in relation to their length

Based on the weakest-link model, a family of fiber strength distributions is investigated assuming a two-stage failure process. At the first stage, a weakest link is formed (instantly or gradually), but at the second one the fracture of this link takes place. The gradual accumulation of flaws is described with the aid of Markov chain theory. The adequacy of the models considered is verified by checking them against experimental strength data for E-glass and flax fibers of various lengths. It is found that the models are not less accurate, but are even better, in a number of cases, than the model based on the known modified Weibull model with a power-law relation between the fiber length and the scale parameter. __________ Translated from Mekhanika Kompozitnykh Materialov, Vol. 42, No. 2, pp. 179–192, March–April, 2006.     

A new lattice model of traffic flow with the consideration of individual difference of anticipation driving behavior

In this paper, we propose a new lattice model of traffic flow with the consideration of individual difference of anticipation driving behavior. The linear stability condition and the mKdV equation are derived from linear stability analysis and nonlinear analysis, respectively. Furthermore, numerical simulation shows that the anticipation driving behavior can increase the cell number of low density, which means that more cars can run freely and traffic congestion can be suppressed efficiently by taking the anticipation driving behavior into account in lattice model. Moreover, with the coefficient of the anticipation driving behavior increasing, the low density region turns wide corresponding to individual difference of anticipation driving behavior.     

Sufficient conditions for the optimal control of a class of systems with continuous lags

Sufficient conditions in the form of a maximum principle are obtained for the optimal control of a system described by integro-differential equations and subject to some specified path constraints. The conditions are relaxed to allow for jumps in the adjoint variables at the junction points, provided a certain convexity hypothesis is satisfied for the constraint set at these points.This research was partially supported at Stanford University by the Office of Naval Research, Contract No. N-00014-67-A-0112-0011, by the National Science Foundation, Grant No. GP-31393, and by the US Atomic Energy Commission, Contract No. AT(04-3)-326-PA-18. It was also supported by the Department of Economics at Rice University.     

A further investigation of a pair of series transformation formulas with applications

As a theoretical completion or a substantial supplement to a recent joint paper by He et al. [Discrete Math. 308 (2008), pp. 3427–3440] containing a pair of series transformation formulas with a variety of illustrative examples, we provide some convergence theorems for the transformation formulas under certain general conditions. We also show that these two transformation formulas subject to the convergence conditions can be further utilized to produce more than 30 special power series sums and combinatorial identities (in a wider sense) mostly not given previously.     

Paths and tableaux descriptions of Jacobi-Trudi determinant associated with quantum affine algebra of type <Emphasis Type="Italic">D</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

We study the Jacobi-Trudi-type determinant which is conjectured to be the q-character of a certain, in many cases irreducible, finite-dimensional representation of the quantum affine algebra of type D _n . Unlike the A _n and B _n cases, a simple application of the Gessel-Viennot path method does not yield an expression of the determinant by a positive sum over a set of tuples of paths. However, applying an additional involution and a deformation of paths, we obtain an expression by a positive sum over a set of tuples of paths, which is naturally translated into the one over a set of tableaux on a skew diagram.