bluuebunny/crossref_metadata_2025 huggingface dataset:
The language of medieval music: two thirteenth-century motets
Authors: Butterfield Ardis
Published: September 2008

The phrase ‘the language of music’, made famous by Deryck Cooke's book of that name, is much repeated in modern music criticism. Is it possible to use this phrase in a medieval context? In what ways is the relationship between music and language in the medieval period best described? The importance of this question is clear when one considers both how high a proportion of medieval music was texted, and conversely, the extent to which the performance of much medieval poetry (even narrative poetry) involved music. We are fortunate that this very large issue has received detailed attention in John Stevens's magisterial account of medieval monophony. My attempt here is to extend the argument into the area of polyphony, concentrating on the nature of compositional activity in thirteenthcentury France. This will include discussion of how far the compositional processes of music and poetry are comparable in this period, and indeed whether they are in any way collaborative. Do the two structural systems – languages, perhaps – of music and words have any effect on each other's system of meaning?
Le Voir Dit and La Messe de Nostre Dame: aspects of genre and style in late works of MacHaut
Authors: Leech-Wilkinson Daniel
Published: September 2008

Le Voir Dit is one of the most fascinating of the works left by the celebrated poet-composer Guillaume de Machaut (d. 1377), and at the same time, as John Stevens has said, ‘one of the most curious documents of the [fourteenth] century’. Through 9000 lines of narrative, sixty-two lyrics in all the main forms (nine of them set to music), and forty-six letters which include comments on the character of the songs and on the business of producing poetry, music and manuscripts, we seem to take a guided tour of Machaut's emotional and professional life over three years of his old age. For more than a century it has proved a rich source of revealing quotations, sustaining many varied arguments. The story it tells of Machaut's literary and emotional affair with a young girl, Peronne, has been read at times as autobiography, at times as fiction; and the incidental comments on composition, performance and copying have been interpreted in studies ranging far beyond Le Voir Dit as evidence of fourteenth-century professional practice. None the less, the constituent parts of the text as they survive in manuscripts from Machaut's circle are disordered, the poem lacks an adequate published edition, and even its music – in size, at least, the most manageable of its components – has yet to be considered as a whole.
Iconography and Liturgy at St Mark's
Authors: Gaston Robert W.
Published: September 2008

Some of the most explicit statements in early Christian and medieval sources about the functions of visual images in churches are notable for their silence regarding the liturgical significance of wall decoration. There is talk of imagery of the Old and New Testaments instructing the laity so that they should know ‘the high deeds of the servants of God and may be prompted to imitate them’, or at least to remember them. Images might be said to ‘decorate with beauty the house of the Lord’, but it is difficult to find it stated anywhere that the monumental cycles that still arrest our gazes in many of the churches were executed to ‘illustrate’, or to ‘represent’, or to ‘dramatize’ the liturgy that was celebrated in those sacred edifices
Two recent editions of Aquitanian polyphony
Authors: Crocker Richard
Published: September 2008

After listening to reports from two observers sent to Vietnam, Kennedy responded with a question. ‘Did you two both go to the same country?’ The reader may ask the same of the two editions to be reviewed here. Each consists of two volumes, all of the same trim size and thickness; but one set is red, the other blue, and the differences go on from there. It is necessary to reassure the reader that both concern the same four documents said to contain ‘Aquitanian polyphony’, and in addition one document known as the ‘Codex Calixtinus’ – more precisely the Liber Sancti Iacobi (of Compostela). The contents include a determinate number of musical compositions, in an indeterminate number of variant versions, all dated to the twelfth century, in France.
Liturgical chant bibliography 3
Authors: Jeffery Peter
Published: September 2008

The study of chant is perhaps at a turning point, with scholars pausing to consolidate recent gains before seeking to move forward once again. One sign of this is the large number of honorific and celebratory volumes devoted to chant studies, including the new Festschrift for Helmut Hucke.
Gregorian studies in the twenty-first century
Authors: Crocker Richard
Published: September 2008

This discussion is ‘after Hiley’: it consists of my reflections, after reading his splendid book, Western Plainchant, concerning what I need and do not need to do, what I want and do not want to do, in pursuing studies in Gregorian chant. Even though my discussion is of some very general issues, it does not offer a programme; on the contrary, it can be taken as a critique of most programmes and systems. None the less, I hope it may suggest to others some positive and fruitful ways of proceeding.
Reconstructing a fragmentary Gloria
Authors: Mitchell Robert J.
Published: September 2008

The idea of reconstructing fragmentary polyphony has not really found a niche in mid-fifteenth-century studies. Whilst editors of Baroque music have become quite used to reconstructing string parts to ‘arie con tre violini’ in skeletal opera sources, and whilst sixteenth-century specialists have occasionally been brave enough to recompose the contents of a lost partbook, this sort of treatment has rarely been applied to fragmentary works of the Dufay and Ockeghem periods. There seem to be two reasons for this. Firstly, since many of the essentials of mid-fifteenth-century style are not based on imitative techniques or the realization of simple chord progressions, the random nature of what an incomplete piece of the period might contain can make plausible reconstruction very difficult. Even the most predictable-looking of complete mid-fifteenth-century works often have surprising rhythmic turns or unexpected progressions, simply because variety was an expected and prized aspect of the mastery of sophisticated polyphony as it was then understood. Secondly, even if an editor achieves what he considers to be a satisfactory reconstruction of such a work, there are few cases of such reconstructions in which there is an overall conjecture rate of less than 20 per cent. Nevertheless, there are exceptions to all generalizations and on the present occasion I believe I have found a movement from a fragmentary cyclic Mass that can be reconstructed with comparatively little conjectural material: the Gloria from theMissa Salve Reginain Munich 3154. This article describes how I became interested in the cycle and suggests how the missing material in its Gloria can be effectively realized.
Phrasing in medieval song: perspectives from traditional music
Authors: Edwards Warwick
Published: September 2008

During the course of a series of articles relating medieval Italian songs to oral and unwritten traditions, Nino Pirrotta comments on a peculiar anonymous two-voice setting from the fourteenth century whose verses seem to have been broken and shattered by the music. Word repetition ‘does not result in a more effective or more understandable rendition of the text; on the contrary, it so fragments and stutters it that any meaning is lost, except as a pretext for the melody which submerges it’. The song in question,Dolce lo mio drudo, is part of a group of unica with Calabrian associations found in the oldest layer of the Reina manuscript. Pirrotta transcribes the song in full and analyses the text and its cognates in detail. It is a ballata with irregularities. I quote in Example 1 just the refrain, together with an indication of the syllable count, in order to facilitate comparison with what follows.
A new canonic Gloria and the changing profile of Dunstaple
Authors: Bent Margaret
Published: September 2008

John Dunstaple's reputation as the most famous English composer of the Middle Ages has stood almost unchallenged since his death. Two epitaphs attributed to one of his patrons, John Wheathamstead, Abbot of St Albans between 1420–40 and 1452–64, give him equal credit as a mathematician and astronomer (or rather, astrologer). Dunstaple was evidently proficient in the quadrivial arts of music, astronomy and mathematics (arithmetic and geometry), but only his musical activities have been thoroughly explored. At least two books that were in his library may provide hints about the level of his attainment in mathematics and astronomy. One is a fascicle within another volume that carries the often quoted ‘Iste libellus pertinebat Johanni Dunstaple cum duci Bedfordie musico’. The other and more extensive of the two manuscripts, Cambridge, Emmanuel College, MS 70, contains treatises on astronomy and astrology by standard authors in various hands. Some of these have what must be a scribal signature (often in the form ‘deo gratias quod Dunstaple’), apparently signalling his own hand for those treatises. If this is indeed the case, we have dozens of folios of closely written Dunstaple autograph and several signatures. His copy of the older astrological treatise by Bartholomew of Parma is copiously illustrated by excellent line-drawings of zodiacal signs and constellations. If these drawings are also in his hand (and they are harmonious with the surrounding script), we must add fine draughtsmanship to his known accomplishments.
Aversa parverse?
Authors: Leech-Wilkinson Daniel
Published: September 2008

PMM 4/2 contained a review by Susan Fast of Matthew Balensuela's new edition of the anonymous fourteenth-century treatise Ars cantus mensurabilis mensurata per modos iuris. Both Balensuela and Fast were struck by the theorist's use of extracts from pieces by Nicholas de Aversa, about whom nothing more is known. The theorist quotes from compositions of others that we do know from surviving sources, including Landini's Donna die d'antor senta and some well-known motets, and in these cases he seems, as Balensuela points out, to be quoting from a rough memory of how the music goes rather than from a copy; his examples never correspond precisely to the music as we know it, yet similar passages in these pieces do illustrate the notational devices he is discussing. Consequently we may not expect to learn much about de Aversa from these (probable mis-)quotations.
Editing Adémar de Chabannes' liturgy for the Feast of St Martial
Authors: Grier James
Published: September 2008

On 3 August 1029, the monks of the abbey of St Martial in Limoges sought to inaugurate a new liturgy for their patron saint, a new liturgy that acknowledged and celebrated his status as an apostle, the younger cousin of Simon Peter, an intimate of Jesus himself, and St Peter's delegate to Gaul.
Liturgical chant bibliography 6
Authors: Paucker Günther Michael
Published: September 2008

From 1992 to 1996 the Liturgical chant bibliography was compiled by Peter Jeffery. His new duties as professor of music at Princeton University will prevent him from continuing his valuable annual listing of chant scholarship. The new author of the bibliography and the editors of Plainsong & Medieval Music would like to take this opportunity to thank him for his unique contribution to this journal over the past four years.
Chant research at the turn of the century and the analytical programme of Helmut Hucke
Authors: Nowacki Edward
Published: September 2008

The end of a century, like the end of any era, is a time to take stock and lay plans. This is no less true of plainsong and medieval music than of any field of human endeavour. So it comes as no surprise to encounter in our professional literature exhortations to re-envision our subject and to contemplate its direction in the twenty-first century. Richard Crocker has been particularly cogent in recommending the abandonment of lost causes and the adoption of new or neglected research methods.1The attempt to read the oldest melodic texts of plainchant as the trace of the sumptuous oral tradition that preceded them, however tantalizing, is ultimately unsatisfying in his view, perhaps even vain. In its place he urges us to cultivate a critical, evaluative understanding of chants composed in the era of musical notation, that is, as authoritative compositions of the time when they were copied rather than as witnesses to an obsolescent oral tradition. Putting this advice into practice would require more listening, performing and remembering of chants as they are and less speculation about how they got that way.
The alleluiasDies sanctificatusandVidimus stellamas examples of late chant transmission
Authors: Hughes David G.
Published: September 2008

It is well known that the two alleluias cited in the title are textings of the same tune – indeed they are only two of many textings of that tune. Along with the alleluiaVideo celos, these two were sung over a rather short space of time in the liturgical year: on the feasts of Christmas, St Stephen's and Epiphany. It happens that for another purpose, involving the transmission of chant in later manuscripts, I have collated the alleluiaDies sanctificatusand alleluiaVidimus stellamin over a hundred manuscripts, most of them late French sources. The choice of these manuscripts rather than others – French rather than German or English – was dictated in part by practical considerations, but also by the conviction that French sources are on the whole richer in variants and hence more revealing in the mechanics of their transmission. The approximately one hundred sources considered are a good majority of the surviving late sources, and the picture they give is, I believe, representative. In the course of this article, I will also have occasion to mention earlier manuscripts, both French and non-French. These are not the primary focus of my study, and therefore I have permitted myself many omissions in that respect. Important graduals, for example from St-Omer,2 Angers3 and Noyon,4 to name only three, have been untouched. My collation has shown a considerable number of variants, some of which are clearly regional in nature, while others are of a more ambiguous character. Having two textings of the same melody available supplies a useful control: readings that occur in both versions naturally have a strong claim to represent a true tradition, rather than a random alteration.
Liturgical chant bibliography 8
Authors: Paucker Gnther Michael
Published: September 2008

Liturgical Chant Bibliography 8 again lists publications covering all aspects of cantus planus, particularly Western chant. In order to present a clear overview of the various types of publications, they have been subdivided into: (1) Editions and facsimile editions, (2) Books and reprints, (3) Congress reports, (4) Chant journals, (5) Collections of essays, dictionaries and periodicals, (6) Articles in periodicals. Access to the contents of the bibliography is facilitated by separate indices of authors, subjects and manuscripts. Prefaced to the bibliography is a list of additions to Liturgical Chant Bibliographies 6 and 7.
Local Expansion of Symmetrical Graphs
Authors: Babai László , Szegedy Mario
Published: September 2008

A graph is vertex-transitive (edge-transitive) if its automorphism group acts transitively on the vertices (edges, resp.). Theexpansion rateof a subsetSof the vertex set is the quotient e(S):= |∂(S)|/|S|, where ∂(S) denotes the set of vertices not inSbut adjacent to some vertex inS. Improving and extending previous results of Aldous and Babai, we give very simple proofs of the following results. LetXbe a (finite or infinite) vertex-transitive graph and letSbe a finite subset of the vertices. IfXis finite, we also assume |S| ≤|V(X)/2. Letdbe the diameter ofSin the metric induced byX. Then e(S) ≥1/(d+ 1); ande(S)≥ 2/(d+2) ifXis finite anddis less than the diameter ofX. IfXis edge-transitive then |δ(S)|/|S| ≥r/(2d), where ∂(S) denotes the set of edges joiningSto its complement andris the harmonic mean of the minimum and maximum degrees ofX. – Diverse applications of the results are mentioned.
Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph
Authors: Godsil C. D.
Published: September 2008

In this work we show that that many of the basic results concerning the theory of the characteristic polynomial of a graph can be derived as easy consequences of a determinantal identity due to Jacobi. As well as improving known results, we are also able to derive a number of new ones. A combinatorial interpretation of the Christoffel-Darboux identity from the theory of orthogonal polynomials is also presented. Finally, we extend some work of Tutte on the reconstructibility of graphs with irreducible characteristic polynomials.
On the Structure of Non-Hamiltonian Graphs I
Authors: Häggkvist Roland
Published: September 2008

The structure of non-Hamiltonian graphs is studied in terms of neighbourhood-unions. Numerous results, such as (A), (B) and (C) below, are obtained.
Choice Numbers of Graphs: a Probabilistic Approach
Authors: Alon Noga
Published: September 2008

The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). By applying probabilistic methods, it is shown that there are two positive constants c1 and c2 such that for all m ≥ 2 and r ≥ 2 the choice number of the complete r-partite graph with m vertices in each vertex class is between c1r log m and c2r log m. This supplies the solutions of two problems of Erdős, Rubin and Taylor, as it implies that the choice number of almost all the graphs on n vertices is o(n) and that there is an n vertex graph G such that the sum of the choice number of G with that of its complement is at most O(n1/2(log n)1/2).
On Subgraph Sizes in Random Graphs
Authors: Calkin Neil , Frieze Alan , McKay Brendan D.
Published: September 2008

For a graph G with m edges let its Range of Subgraph Sizes (RSS)

ρ(G) = {t : G contains a vertex-induced subgraph with t edges}.

G has a full RSS if ρ(G) = {0, 1, …, m}. We establish the threshold for a random graph to have a full RSS and give tight bounds on the likely RSS of a dense random graph.
An Expanded Set of Correlation Tests for Linear Congruential Random Number Generators
Authors: Percus Ora Engelberg , Percus Jerome K.
Published: September 2008

An analytic study is made of the correlation structure of Tausworthe and linear congruential random number generators. The former case is analyzed by the bit mask correlations recently introduced by Compagner. The latter is studied first by an extension to word masks, which include spectral test coefficients as special cases, and then by the bit mask procedure. Although low order bit mask coefficients vanish in both cases, the Tausworthe generator appears to produce a substantially smaller non-vanishing correlation set for large masks – but with larger correlation values – than does the linear congruential.
Random Graph Processes with Degree Restrictions
Authors: Ruciński A. , Wormald N. C.
Published: September 2008

Suppose that a process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always bounded above by d. We prove that if n → ∞ with d fixed, then with probability tending to 1, the final result of this process is a graph with ⌊nd / 2⌋ edges.
Complete Subgraphs of r-partite Graphs
Authors: Jin Guoping
Published: September 2008

The smallest minimal degree of an r-partite graph that guarantees the existence of a complete subgraph of order r has been found for the case r = 3 by Bollobás, Erdő and Szemerédi, who also gave bounds for the cases r ≥ 4. In this paper the exact value is established for the cases r = 4 and 5, and the bounds for r ≥ 6 are improved.
On the Number of Convex Lattice Polygons
Authors: Bárány Imre , Pach János
Published: September 2008

We prove that there are at most {cA1/3} different lattice polygons of area A. This improves a result of V. I. Arnol'd.
A Group-Theoretic Setting for Some Intersecting Sperner Families
Authors: Erdős Péter L. , Faigle Ulrich , Kern Walter
Published: September 2008

Using a group-theoretic approach, we derive some Erdős-Ko-Rado-type results for certain Sperner families of chains and antichains in partial orders. In particular, we establish Bollobás-type inequalities for arbitrary Sperner families of intersecting affine subspaces, and special intersecting Sperner families in generalized Boolean algebras.
Large Induced Subgraphs with All Degrees Odd
Authors: Scott A. D.
Published: September 2008

We prove that every connected graph of order n ≥ 2 has an induced subgraph with all degrees odd of order at least cn/log n, where cis a constant. We also give a bound in terms of chromatic number, and resolve the analogous problem for random graphs.
On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
Authors: Pittel Boris
Published: September 2008

In a set of even cardinalityn, each member ranks all the others in order of preference. A stable matching is a partition of the set inton/2 pairs, with the property that no two unpaired members both prefer each other to their partners under matching. It is known that for some problem instances no stable matching exists. In 1985, Irving found anO(n2) two-phase algorithm that would determine, for any instance, whether a stable matching exists, and if so, would find such a matching. Recently, Tan proved that Irving's algorithm, with a modified second phase, always finds a stable cyclic partition of the members set, which is a stable matching when each cycle has length two. In this paper we study a likely behavior of the algorithm under the assumption that an instance of the ranking system is chosen uniformly at random. We prove that the likely number of basic steps,i.e.the individual proposals in the first phase and the rotation eliminations, involving subsets of members in the second phase, isO(nlogn), and that the likely size of a rotation isO((nlogn)1/2). We establish a ‘hyperbola law’ analogous to our past result on stable marriages. It states that at every step of the second phase, the product of the rank of proposers and the rank of proposal holders is asymptotic, in probability, ton3. We show that every stable cyclic partition is likely to be almost a stable matching, in the sense that at mostO((nlogn)1/2) members can be involved in the cycles of length three or more.
On Extremal Set Partitions in Cartesian Product Spaces
Authors: Ahlswede Rudolf , Cai Ning
Published: September 2008

The partition number of a product hypergraph is introduced as the minimal size of a partition of its vertex set into sets that are edges. This number is shown to be multiplicative if all factors are graphs with all loops included.
Additive and Multiplicative Ramsey Theorems in ℕ – Some Elementary Results
Authors: Bergelson Vitaly , Hindman Neil
Published: September 2008

We show by elementary methods that given any finite partition of the set ℕ of positive integers, there is one cell that is both additively and multiplicatively rich. In particular, this cell must contain a sequence and all of its finite sums, and another sequence and all of its finite products, a fact that was previously known only by utilizing the algebraic structure of the Stone–Čech compactification βℕ of ℕ.
Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains
Authors: Ingrassia Salvatore
Published: September 2008

In this paper we consider the problem of estimating the spectral gap of a reversible Markov chain in terms of geometric quantities associated with the underlying graph. This quantity provides a bound on the rate of convergence of a Markov chain towards its stationary distribution. We give a critical and systematic treatment of this subject, summarizing and comparing the results of the two main approaches in the literature, algebraic and functional. The usefulness and drawbacks of these bounds are also discussed here.
Threshold Channel Graphs
Authors: Kraetzl Miro , Colbourn Charles J.
Published: September 2008

A transformation that increases the blocking probability of the channel graphs arising in interconnection networks is developed. This provides the basis for eminently computing a bound on the blocking probability by applying the transformation to reduce an arbitrary four-stage channel graph to a threshold channel graph. The four-stage channel graph that is most likely to block, given links that are equally likely to block, is characterized. Partial results are proved concerning the threshold channel graphs that are least likely to block.
Threshold Functions for Markov Chains: a Graph Theoretic Approach
Authors: Lynch James F.
Published: September 2008

A new graph theoretic proof of the convergence of Markov chains with variable transition probabilities and a new algorithm for computing the limiting distributions are presented.
Using the Perceptron Algorithm to Find Consistent Hypotheses
Authors: Anthony Martin , Shawe-Taylor John
Published: September 2008

The perceptron learning algorithm quite naturally yields an algorithm for finding a linearly separable boolean function consistent with a sample of such a function. Using the idea of a specifying sample, we give a simple proof that, in general, this algorithm is not efficient.
Image Partition Regularity of Matrices
Authors: Hindman Neil , Leader Imre
Published: September 2008

Many of the classical results of Ramsey Theory, including those of Hilbert, Schur, and van der Waerden, are naturally stated as instances of the following problem: given a u × ν matrix A with rational entries, is it true, that whenever the set ℕ of positive integers is finitely coloured, there must exist some x∈ℕν such that all entries of Ax are the same colour? While the theorems cited are all consequences of Rado's theorem, the general problem had remained open. We provide here several solutions for the alternate problem, which asks that x∈ℕν. Based on this, we solve the general problem, giving various equivalent characterizations.
Extremal Graph Problems for Graphs with a Color-Critical Vertex
Authors: Hundack Christoph , Prömel Hans Jürgen , Steger Angelika
Published: September 2008

In this paper we consider the following problem, given a graph H, what is the structure of a typical, i.e. random, H-free graph? We completely solve this problem for all graphs H containing a critical vertex. While this result subsumes a sequence of known results, its short proof is self contained.
On the Maximum Number of Triangles in Wheel-Free Graphs
Authors: Füredi Zoltán , Goemans Michel X. , Kleitman Daniel J.
Published: September 2008

Gallai [1] raised the question of determiningt(n), the maximum number of triangles in graphs ofnvertices with acyclic neighborhoods. Here we disprove his conjecture (t(n) ~ n2/8) by exhibiting graphs having n2/7.5 triangles. We improve the upper bound [11] of (n2−n)/6 tot(n) ≤;n2/7.02 +O(n). For regular graphs, we further decrease this bound ton2/7.75 +O(n).
Blocking Sets in SQS(2v)
Authors: Gionfriddo Mario , Milici Salvatore , Tuza Zsolt
Published: September 2008

A Steiner quadruple system SQS(v) of order v is a family ℬ of 4-element subsets of a v-element set V such that each 3-element subset of V is contained in precisely one B ∈ ℬ. We prove that if T ∩ B ≠ ø for all B ∈ ℬ (i.e., if T is a transversal), then |T| ≥ v/2, and if T is a transversal of cardinality exactly v/2, then V \ T is a transversal as well (i.e., T is a blocking set). Also, in respect of the so-called ‘doubling construction’ that produces SQS(2v) from two copies of SQS(v), we give a necessary and sufficient condition for this operation to yield a Steiner quadruple system with blocking sets.
A Ramsey-Type Theorem in the Plane
Authors: Nešetřil Jaroslav , Valtr Pavel
Published: September 2008

We show that, for any finite set P of points in the plane and for any integer k ≥ 2, there is a finite set R = R(P, k) with the following property: for any k-colouring of R there is a monochromatic set , ⊆ R, such that is combinatorially equivalent to the set P, and the convex hull of P contains no point of R \ . We also consider related questions for colourings of p-element subsets of R (p > 1), and show that these analogues have negative solutions.
A Rate for the Erdős-Turán Law
Authors: Barbour A. D. , Tavaré Simon
Published: September 2008

The Erdős-Turán law gives a normal approximation for the order of a randomly chosen permutation of n objects. In this paper, we provide a sharp error estimate for the approximation, showing that, if the mean of the approximating normal distribution is slightly adjusted, the error is of order log−1/2n.
A Combinatorial Approach to Complexity Theory via Ordinal Hierarchies
Authors: Deuber Walter A. , Thumser Wolfgang
Published: September 2008

Long regressive sequences in well-quasi-ordered sets contain ascendingsubsequences of lengthn. The complexity of the corresponding functionH(n) is studied in the Grzegorczyk-Wainer hierarchy. An extension to regressive canonical colourings is indicated.
Lattice Points of Cut Cones
Authors: Deza Michel , Grishukhin Viatcheslav
Published: September 2008

Let ℝ+(ℋn),ℤ(ℋn),ℤ+(ℋn) be, respectively, the cone over ℝ, the lattice and the cone over ℤ, generated by all cuts of the complete graph on n nodes. For i ≥ 0, let has exactly i realizations in ℤ+(ℋn)}. We show that is infinite, except for the undecided case and empty and for i = 0, n ≤ 5 and for i ≥ 2, n ≤ 3. The set contains 0,1,∞ nonsimplicial points for n ≤ 4, n = 5, n ≥ 6, respectively. On the other hand, there exists a finite number t(n) such that t(n)d ∈ ℤ+(ℋn) for any ; we also estimate such scales for classes of points. We construct families of points of and ℤ+(ℋn), especially on a 0-lifting of a simplicial facet, and points d ∈ ℝ+(ℋn) with di, n = t for 1 ≤ i ≤ n − 1.
On Triangle Contact Graphs
Authors: de Fraysseix Hubert , de Mendez Patrice Ossona , Rosenstiehl Pierre
Published: September 2008

It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T-or Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.
Properties of Classes of Random Graphs
Authors: Brand Neal , Jackson Steve
Published: September 2008

In [11] it is shown that the theory of almost all graphs is first-order complete. Furthermore, in [3] a collection of first-order axioms are given from which any first-order property or its negation can be deduced. Here we show that almost all Steinhaus graphs satisfy the axioms of almost all graphs and conclude that a first-order property is true for almost all graphs if and only if it is true for almost all Steinhaus graphs. We also show that certain classes of subgraphs of vertex transitive graphs are first-order complete. Finally, we give a new class of higher-order axioms from which it follows that large subgraphs of specified type exist in almost all graphs.
Eigenvalues of Graphs and Sobolev Inequalities
Authors: Chung F. R. K. , Yau S.-T.
Published: September 2008

We derive bounds for eigenvalues of the Laplacian of graphs using discrete versions of the Sobolev inequalities and heat kernel estimates.
The Harmonious Chromatic Number of Almost All Trees
Authors: Edwards Keith
Published: September 2008

A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring.

For any positive integer m, let Q(m) be the least positive integer k such that ≥ m. We show that for almost all unlabelled, unrooted trees T, h(T) = Q(m), where m is the number of edges of T.
Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
Authors: Frieze Alan , Radcliffe A. J. , Suen Stephen
Published: September 2008

We consider the performance of a simple greedy matching algorithm MINGREEDY when applied to random cubic graphs. We show that if λn is the expected number of vertices not matched by MINGREEDY, there are positive constants c1 and c2 such that C1n1/5 ≤ λn ≤ C2n1/5 log n.
On Vertices of Degree n in Minimally n-Edge-Connected Graphs
Authors: Mader W.
Published: September 2008

Let G be a minimally n-edge-connected finite simple graph with vertex number |G| ≥ 2n + 2 + [3/n] and let n ≥ 3 be odd. It is proved that the number of vertices of degree n in G is at least ((n − 1 − ∈n)/(2n + 1))|G| + 2 + 2∈n, where ∈n = (3n + 3)/(2n2 − 3n − 3), and that for every n ≡ 3 (mod 4) this lower bound is attained by infinitely many minimally n-edge-connected finite simple graphs.
On Random 3-sat
Authors: El Maftouhi A. , De La Vega W. Fernandez
Published: September 2008

LetSbe a set ofmclauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} ofnpropositional variables and their negations. Letbe the set of all suchSwithm = cnfor a fixedc> 0. We show, improving significantly over the first moment upper bound, that ifmandntend to infinity with, then almost allare unsatisfiable.
The Smallest Cubic Graphs of Girth Nine
Authors: Brinkmann Gunnar , Mckay Brendan D. , Saager Carsten
Published: September 2008

We describe two computational methods for the construction of cubic graphs with given girth. These were used to produce two independent proofs that the (3,9)-cages, defined as the smallest cubic graphs of girth 9, have 58 vertices. There are exactly 18 such graphs. We also show that cubic graphs of girth 11 must have at least 106 vertices and cubic graphs of girth 13 must have at least 196 vertices.
On the Connectivity of Random k-th Nearest Neighbour Graphs
Authors: Cooper Colin , Frieze Alan
Published: September 2008

Model 1. Consider the complete graph Kn, with vertex set [n] = {1, 2,…, n}, in which each edge e is assigned a length Xe. Colour the k shortest edges incident with each vertex green and the remaining edges blue. The graph made up of the green edges only, will be referred to as the k-th nearest neighbour graph. This graph has been studied in a variety of contexts both computational and statistical.
Isoperimetric Inequalities and Decay of Iterated Kernels for Almost-transitive Markov Chains
Authors: Saloff-Coste L.
Published: September 2008

This paper gives precise isoperimetric inequalities for infinite graphs on which a group acts with finite quotient. Decay estimates are obtained for the iterated kernels of the associated random walks.
An Upper Bound on Zarankiewicz' Problem
Authors: Füredi Zoltán
Published: September 2008

Let ex(n, K3,3) denote the maximum number of edges of a K3,3-free graph on n vertices. Improving earlier results of Kővári, T. Sós and Turán on Zarankiewicz' problem, we obtain that Brown's example for a maximal K3,3-free graph is asymptotically optimal. Hence .
Topological cliques in graphs II
Authors: Komlós János , Szemerédi Endre
Published: September 2008

This note contains a refinement of our paper [8], leading to an alternative proof of a conjecture of Mader and of Erdős and Hajnal recently proved by Bollobás and Thomason.
Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph
Authors: Slivnik Tomaž
Published: September 2008

Recently, Galvin [7] proved that every k-edge-colourable bipartite multigraph is k-edge-choosable. In particular, for a bipartite multigraph G, . Here we give a brief self-contained proof of this result.
Cycle Partitions in Graphs
Authors: Chen C. C. , Jin G. P.
Published: September 2008

In this paper, we prove that every graph contains a cycle intersecting all maximum independent sets. Using this, we further prove that every graph with stability number α is spanned by α disjoint cycles. Here, the empty set, the graph of order 1 and the path of order 2 are all considered as degenerate cycles.
An Almost m-wise Independent Random Permutation of the Cube
Authors: Gowers W. T.
Published: September 2008

We describe a very simple method of randomly permuting the cube {0, 1}n such that the sample space is very small, but, given any m distinct points in {0, 1}n, the images of those points under the random permutation are approximately uniformly distributed over all sequences of m distinct points.
A Phase Transition for the Distribution of Matching Blocks
Authors: Neuhauser Claudia
Published: September 2008

We show distributional results for the length of the longest matching consecutive subsequence between two independent sequencesA1,A2, …,AmandB1,B2, …,Bnwhose letters are taken from a finite alphabet. We assume thatA1,A2, … are i.i.d. with distribution μ andB1,B2, … are i.i.d. with distribution ν. It is known that if μ andvare not too different, the Chen–Stein method for Poisson approximation can be used to establish distributional results. We extend these results beyond the region where the Chen–Stein method was previously successful. We use a combination of ‘matching by patterns’ results obtained by Arratia and Waterman [1], and the Chen–Stein method to show that the Poisson approximation can be extended. Our method explains how the matching is achieved. This provides an explanation for the formulas in Arratia and Waterman [1] and thus answers one of the questions posed in comment F19 in Aldous [2]. Furthermore, in the case where the alphabet consists of only two letters, the phase transition observed by Arratia and Waterman [1] for the strong law of large numbers extends to the distributional result. We conjecture that this phase transition on the distributional level holds for any finite alphabet.
K5-Subdivisions in Graphs
Authors: Thomassen Carsten
Published: September 2008

In 1964 Dirac conjectured that every graph with n vertices and at least 3n − 5 edges contains a subdivision of K5 We prove a weakened version with 7/2;n − 7 instead of 3n − 5. We prove that, for any prescribed vertex νo, the subdivision can be found such that νo is not one of the five branch vertices. This variant of Dirac's problem, which was suggested by the present author in 1973, is best possible in the sense that 7/2;n − 7 cannot be replaced by 7/2;n − 15/2;.
A Winning Strategy for the Ramsey Graph Game
Authors: Pekeč Aleksandar
Published: September 2008

We consider a «Maker-Breaker’ version of the Ramsey Graph Game, RG(n), and present a winning strategy for Maker requiring at most (n − 3)2n−1 + n + 1 moves. This is the fastest winning strategy known so far. We also demonstrate how the ideas presented can be used to develop winning strategies for some related combinatorial games.
Paths, Stars and the Number Three
Authors: Reed Bruce
Published: September 2008

A dominating set for a graph G is a set D of vertices of G such that every vertex of G not in D is adjacent to a vertex of D. We prove that any graph G of minimum degree at least three contains a dominating set D of size at most 3|V(G)|/8. A star S is a graph consisting of a centre x and a set of edges from x to S — x. Clearly, a dominating set D for a graph G corresponds to a set of |D| stars which cover V(G). Thus, we show that the vertices of any graph G of minimum degree 3 can be covered by at most 3|V(G)|/8 vertex disjoint stars. We also show that any connected cubic graph G can be covered by [|V(G)|/9] vertex disjoint paths. Both these results are sharp.
Interval Packing and Covering in the Boolean Lattice
Authors: Engel Konrad
Published: September 2008

Let be the hypergraph whose points are the subsets X of [n] := {1,…,n} with l≤ |X| ≤ u, l < u, and whose edges are intervals in the Boolean lattice of the form I = {C ⊆[n] : X⊆C⊆Y} where |X| = l, |Y| = u, X ⊆ Y.We study the matching number i.e. the the maximum number of pairwise disjoint edges, and the covering number i.e. the minimum number of points which cover all edges. We prove that max and that for every ε > 0 the inequalities hold, where for the lower bounds we suppose that n is not too small. The corresponding fractional numbers can be determined exactly. Moreover, we show by construction that
Restricted Edge-colourings of Bipartite Graphs
Authors: Häggkvist Roland
Published: September 2008

Suppose each vertex of a bipartite multigraph (with partition (X, Y)) is assigned a set of colours; we say this colour scheme is feasible if the edges of the graph can be properly coloured so that each receives a colour in both of its endpoints' sets. We prove various results showing that certain types of colour scheme are always feasible. For instance, we prove that if the colour scheme obtained by assigning the set {1,…, d(x)} of colours to each vertex x of X and the set T = {1,…, t} (t < Δ(X)) to each vertex of Y is feasible, then so is every colour scheme where each vertex x of X gets d(x) colours from T and each vertex of Y gets the set T.
RESPIRATORY DISTRESS SYNDROME
Authors: GREENOUGH ANNE , MURTHY VADIVELAM
Published: September 2008

Respiratory Distress Syndrome (RDS) is due to immaturity of the lungs, primarily the surfactant synthesising system; hence, the risk of RDS is inversely proportional to gestational age. The incidence of RDS has been reduced by the routine use of both antenatal corticosteroids and postnatal surfactant, but still approximately one per cent of babies develop RDS. Hyaline membranes, formed from plasma proteins which have leaked onto the lung surface through damaged capillaries and endothelial cells, line the terminal airways. Hence, RDS has also been called hyaline membrane disease, but RDS is the preferred name as the presence of hyaline membranes can only be confirmed histologically. The aim of this review is to emphasize the pathophysiology of RDS and the clinical presentation and relevance of diagnostic techniques in the current population of very prematurely born infants, highlighting the differential diagnosis. In addition, the evidence base for prophylactic and management strategies including whether new therapies and techniques of respiratory support have positively impacted on outcomes are discussed. The mortality and long term morbidity associated with very premature birth are described. Our increasing understanding that the so-called new bronchopulmonary dysplasia (BPD) and associated chronic adverse respiratory outcomes in such infants can reflect antenatal events resulting in abnormal lung growth is highlighted.
Financial History
Authors: Cassis Y. , Cottrell P. L.
Published: September 2008

The considerable renewal of interest in all aspects of financial history over recent years provided one motivation for this new venture. Yet, the foundations for our specialism, which draws from both History and the Social Sciences, especially economics, have been laid by many. Some would point to continuity in our interest from the publication in the 1930s of jubilee banking history volumes, such as those written for British institutions by Gregory, and by Crick and Wadsworth. Further scholarly momentum came from the studies in comparative banking history undertaken by researchers inspired and brought together by Rondo Cameron from the mid-1960s. Upon these footings and others, financial history has since ‘taken off’ to address an increasingly wider range of issues. This considerable broadening of the specialism, ironically, almost coincided with the decline and then the eventual demise in 1987 of theRevue Internationale d'Histoire de la Banque, founded in 1968. This is not the place to draw up a balance sheet of that journal, which has played a decisive role. Its demise, however, left a gap.Financial History Reviewaims not only to take up its cause, but also to widen the scope of publishing in the field – from banking to financial history – in order to offer the fullest possible support for continuing research.
POETIC: A system for gathering and disseminating traffic information
Authors: Evans R. , Gaizauskas R. , Cahill L. J. , Walker J. , Richardson J. , Dixon A.
Published: September 2008

The Portable Extendable Traffic Information Collator (POETIC) is an information extraction system that extracts traffic information from free text occurring in police incident logs and initiates (simulated) broadcasts of traffic bulletins to motorists when appropriate. POETIC is a second stage prototype system; the initial prototype (TIC, see Evans and Hartley 1990) was limited to the practices and requirements of a single police force. In POETIC, the architecture and data representations have been generalised to make the system tailorable to many different police force ‘domains’. In this paper we describe these developments, and report on tests of the system on authentic input data from three police domains.
The rise of theto-infinitive as verb complement
Authors: Los Bettelou
Published: September 2008

In Old English we find considerable variation in the infinitival complementation patterns of verbs: some verbs take a bare infinitival complement, some verbs take ato-infinitival complement and some verbs can be complemented by either infinitive. This article evaluates two previous attempts to account for the distribution of the two infinitives and offers an alternative account; it also argues that the increase in the use of theto-infinitive occurred mostly at the expense of the finite complement clause rather than at the expense of the bare infinitive, which is the traditional view.
How metaphor affects grammatical coding: the Saxon genitive in computer manuals
Authors: Dabrowska Ewa
Published: September 2008

The distribution of the Saxon genitive and the of genitive in computer manuals is significantly different from their distribution in other texts. This is because the manuals contain a high proportion of computer nouns (nouns referring to computer hardware and software), which pattern like human nouns rather than like inanimate nouns. An analysis of the conventional metaphors used to talk about computers reveals that they are often construed as people, and the higher proportion of the Saxon genitive is a grammatical repercussion of this construal.
Genitives and the creolization question
Authors: Allen Cynthia L.
Published: September 2008

In a recent squib published in this journal, Juhani Klemola notes that there is ample and well-documented evidence for the loss of the genitive inflection in twentieth-century Northern dialect data as well as in early Modern English and Middle English documents representing Northern dialects.
Be going toandwill:a monosemous account
Authors: Nicolle Steve
Published: September 2008

This paper provides an account ofbe going toandwillwithin the framework of Relevance Theory (Sperber & Wilson, 1986, 1995). Because of the range of interpretations derived from the use of these expressions in different contexts, many previous accounts have characterized them as polysemous. This polysemy has been attributed to semantic retention, whereby both old (lexical) and new (grammaticalized) meanings are recovered in certain contexts. The aim of this paper is to demonstrate: (i) that althoughbe going todoes exhibit semantic retention, in a relevance-theoretic framework this does not entail polysemy, and (ii) that interpretations ofwillpreviously attributed to semantic retention are, in fact, pragmatically derived, and hencewillis also monosemous.