A graph G for purposes here is a finite set of elements called vertices and a finite set of elements called edges such that each edge meets exactly two vertices, called the end-points of the edge. An edge is said to join its end-points.

A matching in G is a subset of its edges such that no two meet the same vertex. We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality. This problem was posed and partly solved by C. Berge; see Sections 3.7 and 3.8.

Introduction. The problem discussed in this paper was formulated by T. Harris as follows:

“Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.”

1. Introduction. The equations of dynamics were put into a general form by Lagrange, who expressed them in terms of a set of generalized coordinates and velocities. An alternative general form was later given by Hamilton, in terms of coordinates and momenta. Let us consider the relative merits of the two forms.

Any finite group of linear transformations on n variables leaves invariant a positive definite Hermitian form, and can therefore be expressed, after a suitable change of variables, as a group of unitary transformations (5, p. 257). Such a group may be thought of as a group of congruent transformations, keeping the origin fixed, in a unitary space Un of n dimensions, in which the points are specified by complex vectors with n components, and the distance between two points is the norm of the difference between their corresponding vectors.

Two polynomials θ(G, n) and ϕ(G, n) connected with the colourings of a graph G or of associated maps are discussed. A result believed to be new is proved for the lesser-known polynomial ϕ(G, n). Attention is called to some unsolved problems concerning ϕ(G, n) which are natural generalizations of the Four Colour Problem from planar graphs to general graphs. A polynomial χ(G, x, y) in two variables x and y, which can be regarded as generalizing both θ(G, n) and ϕ(G, n) is studied. For a connected graph χ(G, x, y) is defined in terms of the “spanning” trees of G (which include every vertex) and in terms of a fixed enumeration of the edges.

Let f1 , …, fk be linearly independent real functions on a space X, such that the range R of (f1, …, fk) is a compact set in k dimensional Euclidean space. (This will happen, for example, if the fi are continuous and X is a compact topological space.) Let S be any Borel field of subsets of X which includes X and all sets which consist of a finite number of points, and let C = {ε} be any class of probability measures on S which includes all probability measures with finite support (that is, which assign probability one to a set consisting of a finite number of points), and which are such that

is defined. In all that follows we consider only probability measures ε which are in C.

A well-known theorem of Ramsay (8; 9) states that to every n there exists a smallest integer g(n) so that every graph of g(n) vertices contains either a set of n independent points or a complete graph of order n, but there exists a graph of g(n) — 1 vertices which does not contain a complete subgraph of n vertices and also does not contain a set of n independent points. (A graph is called complete if every two of its vertices are connected by an edge; a set of points is called independent if no two of its points are connected by an edge.) The determination of g(n) seems a very difficult problem; the best inequalities for g(n) are (3)

It is not even known that g(n)1/n tends to a limit. The lower bound in (1) has been obtained by combinatorial and probabilistic arguments without an explicit construction.

Maximum of a square-free quadratic form on a simplex. The following question was suggested by a problem of J. E. MacDonald Jr. (1):

Given a graph G with vertices 1, 2, . . . , n. Let S be the simplex in En given by xi ≥ 0, Σxi = 1. What is

Let < be a non-reflexive partial ordering defined on a set P. Let G(P, <) be the undirected graph whose vertices are the elements of P, and whose edges (a, b) connect vertices for which either a < b or b < a. A graph G with vertices P for which there exists a partial ordering < such that G = G(P, <) is called a comparability graph.

In §2 we state and prove a characterization of those graphs, finite or infinite, which are comparability graphs. Another proof of the same characterization has been given in (2), and a related question examined in (6). Our proof of the sufficiency of the characterization yields a very simple algorithm for directing all the edges of a comparability graph in such a way that the resulting graph partially orders its vertices.

Let V be a connected, compact, differentiable Riemannian manifold. If V is not closed we denote its boundary by S. In terms of local coordinates (xi), i = 1, 2, … Ν, the line-element dr is given by where gik (x1, x2, … xN) are the components of the metric tensor on V We denote by Δ the Beltrami-Laplace-Operator and we consider on V the differential equation (1) Δu + λu = 0.

This paper deals with finite sequences of integers. Typical of the problems we shall treat is the determination of the number of sequences of length n, consisting of the integers 1, 2, … , m, which have a longest increasing subsequence of length α. Throughout the first part of the paper we will deal only with sequences in which no numbers are repeated. In the second part we will extend the results to include the possibility of repetition. Our results will be stated in terms of standard Young tableaux.

This paper is concerned with a matrix A of m rows and n columns, all of whose entries are 0's and l's. Let the sum of row i of A be denoted by ri (i = 1, … , m) and let the sum of column i of A be denoted by si (i = 1, … , n).

In the series of "Census" papers, of which this is the fourth, we attempt to lay the groundwork of an enumerative theory of planar maps (12, 13, 14). The maps concerned are rooted in the sense that some edge is fixed as the root, and a positive sense of description and right and left sides are specified for it. This device simplifies the theory by ruling out the possibility of a map being symmetrical.

Soit K un espace compact, C(K) l'espace des fonctions complexes continues sur K, muni de la norme uniforme, son dual (espace des mesures de Radon sur K). Cet article est consacré essentiellement à l'étude des applications linéaires faiblement compactes de C(K) dans des espaces localement convexes F quelconques i.e. les applications linéaires qui transforment la boule unité de C(K) en une partie faiblement relativement compacte de F.

In various numerical problems one is confronted with the task of solving a system of linear inequalities:

(1.1) (i = 1, … ,m)

assuming, of course, that the above system is consistent. Sometimes one has, in addition, to minimize a given linear form l(x). Thus, in linear programming one obtains a problem of the latter type.

Let A be a closed set of points in the n-dimensional euclidean space En. If p and p1 are points of En such that

1.1

then p1 is said to be point-wise closer than p to the set A. If p is such that there is no point p1 which is point-wise closer than p to A, then p is called a closest point to the set A.

Let P be a closed region in the plane bounded by a simple closed curve, and let S be a simplicial dissection of P. We may say that S is a dissection of P into a finite number α of triangles so that no vertex of any one triangle is an interior point of an edge of another. The triangles are ‘'topological” triangles and their edges are closed arcs which need not be straight segments. No two distinct edges of the dissection join the same two vertices, and no two triangles have more than two vertices in common.

For the purpose of analysing bipartite graphs (hereinafter called simply graphs) the concept of an exterior covering is introduced. In terms of this concept it is possible in a natural way to decompose any graph into two parts, an inadmissible part and a core. It is also possible to decompose the core into irreducible parts and thus obtain a canonical reduction of the graph. The concept of irreducibility is very easily and naturally expressed in terms of exterior coverings. The role of the inadmissible edges of a graph is to obstruct certain natural coverings of the graph.

Root systems and Coxeter groups are important tools in multivariable analysis. This paper is concerned with differential-difference and integral operators, and orthogonality structures for polynomials associated to Coxeter groups. For each such group, the structures allow as many parameters as the number of conjugacy classes of reflections. The classical orthogonal polynomials of Gegenbauer and Jacobi type appear in this theory as two-dimensional cases. For each Coxeter group and admissible choice of parameters there is a structure analogous to spherical harmonics which relies on the connection between a Laplacian operator and orthogonality on the unit sphere with respect to a group-invariant measure. The theory has been developed in several papers of the author [4,5,6,7]. In this paper, the emphasis is on the study of an intertwining operator which allows the transfer of certain results about ordinary harmonic polynomials to those associated to Coxeter groups. In particular, a formula and a bound are obtained for the Poisson kernel.

Studies of optimization problems and certain kinds of differential equations have led in recent years to the development of a generalized theory of differentiation quite distinct in spirit and range of application from the one based on L. Schwartz's “distributions.” This theory associates with an extended-real-valued function ƒ on a linear topological space E and a point x ∈ E certain elements of the dual space E* called subgradients or generalized gradients of ƒ at x. These form a set ∂ƒ(x) that is always convex and weak*-closed (possibly empty). The multifunction ∂ƒ: x →∂ƒ(x) is the sub differential of ƒ.

Rules that relate ∂ƒ to generalized directional derivatives of ƒ, or allow ∂ƒ to be expressed or estimated in terms of the subdifferentials of other functions (whenƒ = ƒ1 + ƒ2,ƒ = g o A, etc.), comprise the sub differential calculus.