Dense Packing of Patterns in a Permutation

We study the length L _k of the shortest permutation containing all patterns of length k. We establish the bounds e ⁻² k ² < L _k ≤ (2/3 + o(1))k ². We also prove that as k → ∞, there are permutations of length (1/4 + o(1))k ² containing almost all patterns of length k. Received January 2, 2007     

A regular decomposition of the edge-product space of phylogenetic trees

We investigate the topology and combinatorics of a topological space called the edge-product space that is generated by the set of edge-weighted finite labelled trees. This space arises by multiplying the weights of edges on paths in trees, and is closely connected to tree-indexed Markov processes in molecular evolutionary biology. In particular, by considering combinatorial properties of the Tuffley poset of labelled forests, we show that the edge-product space has a regular cell decomposition with face poset equal to the Tuffley poset.     

The Number of M-Sequences and f-Vectors

M -sequences (a.k.a. f-vectors for multicomplexes or O-sequences) in terms of the number of variables and a maximum degree. In particular, it is shown that the number of M-sequences for at most 2 variables are powers of two and for at most 3 variables are Bell numbers. We give an asymptotic estimate of the number of M-sequences when the number of variables is fixed. This leads to a new lower bound for the number of polytopes with few vertices. We also prove a similar recursive formula for the number of f-vectors for simplicial complexes. Keeping the maximum degree fixed we get the number of M-sequences and the number of f-vectors for simplicial complexes as polynomials in the number of variables and it is shown that these numbers are asymptotically equal. Received: February 28, 1996/Revised: February 26, 1998     

The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

The minimal weight of a spanning tree in a complete graph K_n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.     

Application of simca multivariate data analysis to the classification of gas chromatographic profiles of human brain tissues

Sixteen samples of three types (classes) of brain tissue were characterized by capillary gas chromatography (g.c.). Each sample is thus characterized by the peak heights of 105 peaks in each g.c. profile. SIMCA pattern recognition is used to analyze the 16 × 105 data matrix in order to differentiate between the three classes on the basis of the g.c. data only. The SIMCA method is therefore applicable even when the number of variables (105) exceeds the number of objects (16). The results indicate that g.c. profiles are useful for the identification of brain tissue type.     

The correlogram: a visual display of periodicity

Fundamental frequency (F0) extraction is often used in voice quality analysis. In pathological voices with a high degree of instability in F0, it is common for F0 extraction algorithms to fail. In such cases, the faulty F0 values might spoil the possibilities for further data analysis. This paper presents the correlogram, a new method of displaying periodicity. The correlogram is based on the waveform-matching techniques often used in F0 extraction programs, but with no mechanism to select an actual F0 value. Instead, several candidates for F0 are shown as dark bands. The result is presented as a 3D plot with time on the x axis, correlation delay inverted to frequency on the y axis, and correlation on the z axis. The z axis is represented in a gray scale as in a spectrogram. Delays corresponding to integer multiples of the period time will receive high correlation, thus resulting in candidates at F0, F0/2, F0/3, etc. While the correlogram adds little to F0 analysis of normal voices, it is useful for analysis of pathological voices since it illustrates the full complexity of the periodicity in the voice signal. Also, in combination with manual tracing, the correlogram can be used for semimanual F0 extraction. If so, F0 extraction can be performed on many voices that cause problems for conventional F0 extractors. To demonstrate the properties of the method it is applied to synthetic and natural voices, among them six pathological voices, which are characterized by roughness, vocal fry, gratings/scrape, hypofunctional breathiness and voice breaks, or combinations of these.     

Image analysis and chemical information in images

Image analysis and its different aspects are presented with emphasis on the difference between technology, conceptual modelling (psychology) and chemical information. An overview is given of how the information in image analysis is presented. The distinction between univariate and multivariate image analysis is taken up. The different data analysis techniques that are in common in both chemometrics and image analysis play a major role here.     

Multiple excitations in the core photoelectron spectrum of acetylene

A high-resolution core photoelectron spectrum of free acetylene is presented. Configuration interaction and complete active space SCF calculations were carried out for assignment and prediction of energies and intensities in the spectrum. The shake-up structure is found to be strongly dominated by intervalence π_g to π_g transitions for which multiple 2-, 3- and 4-fold excitations are important.