Cycles Through 23 Vertices in 3-Connected Cubic Planar Graphs

 We establish that if A is a set of at most 23 vertices in a 3-connected cubic planar graph G, then there is a cycle in G containing A. This result is sharp. Revised: September 1, 1997     

The degree sequence of a random graph. I. The models

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and ½m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X₁,…,X_n) | ∑ X_i=m}, where X₁,…,X_n are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p=p(n), the distribution of the degree sequence can be approximated by {(X₁,…,X>_n) | ∑ X_i is even}, where X₁,…,X_n are independent random variables each having the distribution Binom (n−1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n^−k for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t=t(n) as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 97–117 (1997)     

Decoupling the NLO coupled DGLAP evolution equations: an analytic solution to pQCD

Using repeated Laplace transforms, we turn coupled, integral-differential singlet DGLAP equations into NLO (next-to-leading) coupled algebraic equations, which we then decouple. After two Laplace inversions we find new tools for pQCD: decoupled NLO analytic solutions $F_{s}(x,Q^{2})={\mathcal{F}}_{s}(F_{s0}(x),G_{0}(x))$ , $G(x,Q^{2})={\mathcal{G}}(F_{s0}(x), G_{0}(x))$ . ${\mathcal{F}}_{s}$ , $\mathcal{G}$ are known NLO functions and $F_{s0}(x)\equiv F_{s}(x,Q_{0}^{2})$ , $G_{0}(x)\equiv G(x,Q_{0}^{2})$ are starting functions for evolution beginning at $Q^{2}=Q_{0}^{2}$ . We successfully compare our u and d non-singlet valence quark distributions with MSTW results (Martin et al., Eur. Phys. J. C 63:189, 2009).     

Kinetic frustration of Ostwald ripening in Ge/Si(100) hut ensembles

We show that low area density Ge/Si(100) island ensembles comprised solely of hut and pyramid clusters do not undergo Ostwald ripening during days-long growth temperature anneals. In contrast, a very low density of large, low chemical potential Ge islands reduce the supersaturation causing the huts and pyramids to ripen. By assuming that huts lengthen by adding single {105} planes that grow from apex-to-base, we use a mean-field facet nucleation model to interpret these experimental observations. We find that each newly completed plane replenishes the nucleation site at the hut apex and depletes the Ge supersaturation by a fixed amount. This provides a feedback mechanism that reduces the island growth rate. As long as the supersaturation remains high enough to support nucleation of additional planes on the narrowest hut cluster, Ostwald ripening is suppressed on an experimental time scale.     

Mass measurements of increased accuracy resolve heterogeneous populations of intact ribosomes

It is established that noncovalent complexes can be maintained both during and after electrospray and that assemblies of increasing size and complexity often lead to broadened peaks in mass spectra. This broadening arises from the tendency of large protein assemblies to form adducts with salts and is compounded when complexes are isolated directly from cells, without the full protein complement. To investigate the origins of this broadening in mass spectral peaks and to develop the optimal method for analyzing mass spectra of large protein complexes, we have carried out a systematic investigation of a series of noncovalent complexes representing a range of different sizes and architectures. We establish a positive correlation between peak width and the increased mass observed and show that this correlation is independent of the instrumental parameters employed. Using this relationship we show that we can determine masses of both 30S subunits and intact 2.3 MDa 70S ribosomes from Thermus thermophilus. The masses of both particles are consistent with multiple populations of ribosomes. To identify these various populations we combine simulated mass spectra of ribosomes, with and without the full protein complement, and estimate the extent of adducts from our study of known complexes. The results allow us to determine the contribution of the different subpopulations to the overall mass spectrum. We confirm the existence of these subpopulations using tandem mass spectrometry of intact 30S subunits. Overall, the results show that, rather than uniform particles, gas-phase ribosomes consist of a number of discrete populations. More generally, the results establish a rigorous procedure for accurate mass measurement and spectral analysis of heterogeneous macromolecular assemblies.     

Wythoff partizan subtraction

We introduce a class of normal-play partizan games, called Complementary Subtraction. These games are instances of Partizan Subtraction where we take any set A of positive integers to be Left’s subtraction set and let its complement be Right’s subtraction set. In wythoff partizan subtraction we take the set A and its complement B from wythoff nim, as the two subtraction sets. As a function of the heap size, the maximum size of the canonical forms grows quickly. However, the value of the heap is either a number or, in reduced canonical form, a switch. We find the switches by using properties of the Fibonacci word and standard Fibonacci representations of integers. Moreover, these switches are invariant under shifts by certain Fibonacci numbers. The values that are numbers, however, are distinct, and we can find their binary representation in polynomial time using a representation of integers as sums of Fibonacci numbers, known as the ternary (or “the even”) Fibonacci representation.     

Forward masking as a method of measuring place specificity of neural excitation in cochlear implants: a review of methods and interpretation

This paper reviews the psychophysical forward masking methods that have been used to investigate place specificity in cochlear implantees. These experiments are relevant for investigating whether the individual variability in outcomes for people using the same device can be explained by individual variations in frequency resolution or whether place specificity is affected by different modes of stimulation (such as bipolar, monopolar or tripolar) in the same person. Unfortunately, there has been no consensus about the methods used to derive electrical forward masking functions, or in the way that they are interpreted in relation to place specificity. Here, the different methods are critically examined to provide insight into the optimal methods that should be used to measure and interpret spatial forward masking functions in electric hearing. It is shown that, in order to separate the temporal effects of masking decay from the place-specificity information, different analyses of the functions are needed depending on whether a fixed-probe or fixed-masker method is employed. The effects of unit of measurement on specificity measures and the effects of subject listening strategy on the forward masked functions are also discussed.     

The number of transversals in a Latin square

A Latin Square of order n is an n × n array of n symbols, in which each symbol occurs exactly once in each row and column. A transversal is a set of n entries, one selected from each row and each column of a Latin Square of order n such that no two entries contain the same symbol. Define T(n) to be the maximum number of transversals over all Latin squares of order n. We show that for n ≥ 5, where b ≈ 1.719 and c ≈ 0.614. A corollary of this result is an upper bound on the number of placements of n non-attacking queens on an n × n toroidal chess board. Some divisibility properties of the number of transversals in Latin squares based on finite groups are established. We also provide data from a computer enumeration of transversals in all Latin Squares of order at most 9, all groups of order at most 23 and all possible turn-squares of order 14.     

The non-abelian simple groups g, |g| < 105— presentations

Of the 56 isomorphism classes of simple groups of order up to 10⁶ there are 10 of order up to 10⁵ distinct from PSL(2,q). Presentations for these groups are given here in the form G = < a, b; a² = b^m = 1, {r_i (a, b)}_iεI = 1 > where m is minimal (with respect to a). They are complete in the sense that any pair (a, b) of generators of G satisfying the relations a² = b^m = 1, with m minimal, will satisfy the defining relations of just one presentation listed here.     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.