Ballots and plane trees

The correspondence of certain plane trees and binary sequences reported by D. A. Klarner in [1], and a ballot interpretation of the latter, are used to make an independent evaluation of the number of classes of isomorphic, (k + 1)-valent, planted plane trees with kn + 2 points. This provides an interesting multivariable identity for binomial coefficients.     

Achiral plane trees

Harary and Robinson showed that the number a_n of achiral planted plane trees with n points coincides with the number p_n of achiral plane trees with n points, for n ? 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two-to-one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2a_n = 2p_n. Answers are also supplied to similar correspondence-type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.     

The butterfly decomposition of plane trees

We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition, which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schröder paths. The classical Chung-Feller theorem as well as some generalizations and variations follow quickly from the butterfly decomposition. We next obtain two involutions on free Dyck paths and free Schröder paths, leading to parity results and combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of Klazar's generating function for the number of chains in plane trees. Finally we study the total size of chains in plane trees with n edges and show that the average size of such chains tends asymptotically to (n+9)/6.     

Imprimitive distance-regular graphs and projective planes

We investigate a class of (imprimitive) covering graphs Γ of complete bipartite graphs K_k,k and show that they are in one-to-one correspondence with triples (P, l, P), where P is a projective plane of order k and (l, P) is a distinguished flag of P. If Γ is distance-transitive, then P ? l is a self-dual rank three translation plane and may be coordinatised by a semifield.     

Partition and composition matrices

This paper introduces two matrix analogues for set partitions. A composition matrix on a finite set X is an upper triangular matrix whose entries partition X, and for which there are no rows or columns containing only empty sets. A partition matrix is a composition matrix in which an order is placed on where entries may appear relative to one-another.We show that partition matrices are in one-to-one correspondence with inversion tables. Non-decreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are s-diagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfer-matrix method and are equinumerous with permutations which are sortable by two pop-stacks in parallel.We show that composition matrices on X are in one-to-one correspondence with (2+2)-free posets on X. Also, composition matrices whose rows satisfy a column-ordering relation are shown to be in one-to-one correspondence with parking functions. Finally, we show that pairs of ascent sequences and permutations are in one-to-one correspondence with (2+2)-free posets whose elements are the cycles of a permutation, and use this relation to give an expression for the number of (2+2)-free posets on {1,…,n}.     

Lie algebroid structures on double vector bundles and representation theory of Lie algebroids

A VB-algebroid is essentially defined as a Lie algebroid object in the category of vector bundles. There is a one-to-one correspondence between VB-algebroids and certain flat Lie algebroid superconnections, up to a natural notion of equivalence. In this setting, we are able to construct characteristic classes, which in special cases reproduce characteristic classes constructed by Crainic and Fernandes. We give a complete classification of regular VB-algebroids, and in the process we obtain another characteristic class of Lie algebroids that does not appear in the ordinary representation theory of Lie algebroids.     

Closure operators I

Closure operators in an (E, M)-category X are introduced as concrete endofunctors of the comma category whose objects are the elements of M. Various kinds of closure operators are studied. There is a Galois equivalence between the conglomerate of idempotent and weakly hereditary closure operators of X and the conglomerate of subclasses of M which are part of a factorization system. There is a one-to-one correspondence between the class of regular closure operators and the class of strongly epireflective subcategories of X. Every closure operators admits an idempotent hull and a weakly hereditary core.Various examples of additive closure operators in Top are given. For abelian categories standard closure operators are considered. It is shown that there is a one-to-one correspondence between the class of standard closure operators and the class of preradicals. Idempotent, weakly hereditary, standard closure operators correspond to idempotent radicals (= torsion theories).     

Trace au bord latéral des solutions positives d'équations paraboliques non linéaires

Let us consider the equation (PE): in Q_T B x (0, T), where B is the open unit ball in R^N. We show that every positive solution u possesses a uniquely defined trace on ∂₁Q_T = ∂B x (0, T), given by a positive, regular Borel measure (not necessarily a Radon measure). If, there exists a one-to-one correspondence between the set of measures as above and the set of positive solutions of (PE) vanishing for t = 0.     

Toric Anti-self-dual 4-manifolds Via Complex Geometry

Using the twistor correspondence, this article gives a one-to-one correspondence between germs of toric anti-self-dual conformal classes and certain holomorphic data determined by the induced action on twistor space. Recovering the metric from the holomorphic data leads to the classical problem of prescribing the ?ech coboundary of 0-cochains on an elliptic curve covered by two annuli. The classes admitting Kähler representatives are described; each such class contains a circle of Kähler metrics. This gives new local examples of scalar flat Kähler surfaces and generalises work of Joyce [Duke. Math. J. 77(3), 519–552 (1995)] who considered the case where the distribution orthogonal to the torus action is integrable.     

Enumeration of coloured plane trees with a given type partition

Tutte's result for the number of planted plane trees with a given degree partition is rederived by a variety of methods and in particular by a simple piecewise construction technique. A theorem of Gordon and Temple is applied in order to give a general relationship between the number of planted plane trees and the number of rooted plane trees and the degree partition restriction is generalised to type partition. The piecewise construction method is successfully used to derive the number of planted plane trees with a given 2-colour degree partition, also derived by Tutte, and an algorithm for the k-coloured case is developed. This algorithm may be used to obtain more specific results. These models are relevant to the statistical mechanics of polymers and this is discussed briefly.     

Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium

We consider an n-player finite strategic game. The payoff vector of each player is a random vector whose distribution is not completely known. We assume that the distribution of a random payoff vector of each player belongs to a distributional uncertainty set. We define a distributionally robust chance-constrained game using worst-case chance constraint. We consider two types of distributional uncertainty sets. We show the existence of a mixed strategy Nash equilibrium of a distributionally robust chance-constrained game corresponding to both types of distributional uncertainty sets. For each case, we show a one-to-one correspondence between a Nash equilibrium of a game and a global maximum of a certain mathematical program.     

Chord calculus and stochastic geometry

Chord calculus is a collection of integration procedures applied to to the combinatorial decompositions that give the solution of the Buffon-Sylvester problem for n needles in a plane or the similar problem in IR ³. It is a source of various integral geometry identities, some of which find their application in Stochastic geometry. In the present paper these applications are focused on random convex polygons and polyhedrons, where we define certain classes where rather simple tomography analysis is possible. The choice of these classes (the Independent Angles class and the Independent Orientations class) is due to the nature of the results of the Chord calculus. The last section points at an application of the convex polygons from the Independent Angles class to Boolean sets in the plane (Boolean models) whose probability distibutions are invariant with respect to the group of Euclidean motions of the plane.     

Kernel systems on L-ordered sets

This paper presents fuzzy versions of kernel operators and kernel systems on L-ordered sets and establishes a one-to-one correspondence between them.     

Trees with extremal numbers of maximal independent sets including the set of leaves

A subset S of vertices of a graph G is independent if no two vertices in S are adjacent. In this paper we study maximal (with respect to set inclusion) independent sets in trees including the set of leaves. In particular the smallest and the largest number of these sets among n-vertex trees are determined characterizing corresponding trees. We define a local augmentation of trees that preserves the number of maximal independent sets including the set of leaves.     

Train tracks with C 1+ self-renormalizable structures

We prove a one-to-one correspondence between C ¹⁺  conjugacy classes of diffeomorphisms with hyperbolic sets contained in surfaces and stable and unstable pairs of one-dimensional C ¹⁺  self-renormalizable structures.     

Forms of pointed Hopf algebras

Using descent theory, we study Hopf algebra forms of pointed Hopf algebras. It turns out that the set of isomorphism classes of such forms are in one-to-one correspondence to other known invariants, for example the set of isomorphism classes of Galois extensions with a certain group F, or the set of isometry classes of m-ary quadratic forms. Our theory leads to a classification of all Hopf algebras over a field of characteristic zero that become pointed after a base extension, in dimension p, p ² and p ³, with p odd. Received: 22 November 1998     

Representative graphs of r-regular partial planes and representation of orthomodular posets

In this paper the authors establish a one-to-one correspondence between the isomorphism classes of graphs whose structure spaces are r-regular partial planes and the isomorphism classes of graphs which have no induced subgraphs isomorphic to an (r + 1)-pointed star or to K₄ with a single line removed. Moreover the graphs whose structure space contains no 4-loops correspond to graphs with no 4-cycles as induced subgraphs. It is pointed out that these graphs give rise to orthomodular posets (or lattices in the case of no 4-loops) and hence are of much interest in the study of orthomodular structures and in particular of quantum logics.     

Classification of convolutional codes

Convolutional codes have the structure of an F[z]-module. To study their properties it is desirable to classify them as the points of a certain algebraic variety. By considering the correspondence of submodules and the points of certain quotient schemes, and the inclusion of these as subvarieties of certain Grassmannians, one has a one-to-one correspondence of convolutional codes and the points of these subvarieties. This classification of convolutional codes sheds light on their structure and proves to be helpful to give bounds on their free distance and to define convolutional codes with good parameters.     

Dirac structures and paracomplex manifolds

We introduce the notion of a generalized paracomplex structure. This is a natural notion which unifies several geometric structures such as symplectic forms, paracomplex structures, and Poisson structures. We show that generalized paracomplex structures are in one-to-one correspondence with pairs of transversal Dirac structures on a smooth manifold. To cite this article: A. Wade, C. R. Acad. Sci. Paris, Ser. I 338 (2004).