Note on Halin's theorem on minimally connected graphs

In this note it is shown that any finite directed graph of strong connectivity n contains either a vertex with indegree n, a vertex with outdegree n, or an edge whose removal does not decrease the connectivity. This is a directed graph counterpart of Halin's theorem on undirected graphs. It is pointed out that only a few preparations and modifications are necessary to make his proof valid for directed graphs.     

On Schmerl's effective version of Brooks' theorem

A new proof is given of Schmerl's recent result that a highly recursive graph G with χ(G) ≤ k according to Brooks' theorem, has a recursive k-colouring.     

Connectedness and classification of certain graphs

G. A. Dirac gives a necessary arc family condition for a graph to be n-vertex connected. The converse of this theorem of Dirac is false. Mesner and Watkins obtained partial results for additional conditions that the converse be true. A graph G which satisfies Dirac's arc family condition is now completely classified in terms of the order of V(G), the structure of parts of minimum cutsets of G and consequent lower bounds for vertex-connectivity of G. Examples show that all lower bounds are best possible. Several distinct extensions of Whitney's necessary and sufficient condition for a graph to be n-vertex connected also appear as corollaries. Finally, examples are presented to show a graph which satisfies a given n-family arc condition. However, the same graph does not satisfy a very similar (n ? 1)-family arc condition where exactly one arc has been eliminated from the statement of the original n-family arc conditon.     

Schur functions,Good's identity,and hypergeometric series well poised in SU(n)

A simple direct proof is given of a fundamental identity involving Schur functions which contains as special cases the identity responsible for Good's proof of the Dyson conjecture and the summation theorem of Biedenharn and Louck that appears frequently in dealing with the explicit matrix elements which arise in the unitary groups. By using the Weyl character formula, a general identity is obtained which implies our result involving Schur functions when a root system of type A_{n ? 1} is considered. As a further application of our general identity, explicit analogs of Good's identity are given, corresponding to the root systems of types B_n, C_n, and D_n. In addition, methods to obtain q-analogs of all of these results are briefly described.     

Characterizations of products of symmetric matrices

Characterizations are obtained for matrices C of the form C = AΣ, where A, Σ are n×n matrices over the real field such that A is symmetric and C is nonnegative definite. Among others, a proof of recent generalization of Cochran's theorem is given.     

A short proof of Meyniel's theorem

Meyniel's theorem states that a strict diconnected digraph has a directed Hamilton cycle if d(u) + d(v) ? 2n ? 1 for every pair u, v of nonadjacent vertices. We give short proof of this theorem.     

Degrees and matchings

Let n, b, d be positive integers. We evaluate f(n, b, d), the largest possible number of edges in a graph with n vertices having no vertex of degree greater than d and no set of more than b independent edges. Our proof technique has a linear programming flavor and uses Berge's matching formula.     

On the maximal order of cyclicity of antisymmetric directed graphs

A directed graph G without loops or multiple edges is said to be antisymmetric if for each pair of distinct vertices of G (say u and v), G contains at most one of the two possible directed edges with end-vertices u and v. In this paper we study edge-sets M of an antisymmetric graph G with the following extremal property: By deleting all edges of M from G we obtain an acyclic graph, but by deleting from G all edges of M except one arbitrary edge, we always obtain a graph containing a cycle. It is proved (in Theorem 1) that if M has the above mentioned property, then the replacing of each edge of M in G by an edge with the opposite direction has the same effect as deletion: the graph obtained is acyclic. Further we study the order of cyclicity of G (= theminimalnumberofedgesinsuchasetM) and the maximal order of cyclicity in an antisymmetric graph with given number n of vertices. It is shown that for n < 10 this number is equal to the maximal number of edge-disjoint circuits in the complete (undirected) graph with n vertices and for n = 10 (and for an infinite set of n's) the first number is greater than the latter.     

A characterization of permutations via skew-hooks

A characterization of permutations is given using skew-hooks, such that the r-descents of the permutation are reflected in the structure of the skew-hook. The characterization yields a combinatorial proof of Foulkes' skew-hook rule for computing Eulerian numbers.     

A new proof of the equivalence of injectivity and hyperfiniteness for factors on a separable Hilbert space

In 1975 A. Connes proved the fundamental result that injective factors on a separable Hilbert space are hyperfinite. In this paper a new proof of this result is presented in which the most technical parts of Connes proof are avoided. Particularly the proof does not rely on automorphism group theory. The starting point in this approach is Wassermann's simple proof of injective ? semidiscrete together with Choi and Effros' characterization of semidiscrete von Neumann algebras as those von Neumann algebras N for which the identity map on N has an approximate completely positive factorization through n × n-matrices.     

The diagonal hypergraph of a matrix (bipartite graph)

Let A be an n x n matrix of 0's and 1's (a bipartite graph). The diagonal hypergraph of A is the hypergraph whose vertices correspond to the 1's (edges) of A and whose edges correspond to the positive diagonals (1-factors) of A. The numerical invariants of this hypergraph are investigated.     

On monochromatic paths in edge-coloured digraphs

Let G be a directed graph whose edges are coloured with two colours. Call a set S of vertices of Gindependent if no two vertices of S are connected by a monochromatic directed path. We prove that if G contains no monochromatic infinite outward path, then there is an independent set S of vertices of G such that, for every vertex x not in S, there is a monochromatic directed path from x to a vertex of S. In the event that G is infinite, the proof uses Zorn's lemma. The last part of the paper is concerned with the case when G is a tournament.     

Intersection theory for graphs

An intersection theory developed by the author for matroids embedded in uniform geometries is applied to the case when the ambient geometry is the lattice of partitions of a finite set so that the matroid is a graph. General embedding theorems when applied to graphs give new interpretations to such invariants as the dichromate of Tutte. A polynomial in n + 1 variables, the polychromate, is defined for graphs with n vertices. This invariant is shown to be strictly stronger than the dichromate, it is edge-reconstructible and can be calculated for proper graphs from the polychromate of the complementary graph. By using Tutte's construction for codichromatic graphs (J. Combinatorial Theory 16 (1974), 168–174), copolychromatic (and therefore codichromatic) graphs of arbitrarily high connectivity are constructed thereby solving a problem posed in Tutte's paper.     

On the range of recurrent Markov chains

Let {X_n}₀^∞ be an irreducible recurrent Markov Chain on the nonnegative integers. A result of Chosid and Isaac (1978) gives a sufficient condition for n^?1R_n → 0 w.p.1. where R_n is the range of the chain. We give an alternative proof using Kingman's subadditive ergodic theorem (Kingman, 1973). Some examples are also given.     

The longest path in a random graph

A random graph with (1+ε)n/2 edges contains a path of lengthcn. A random directed graph with (1+ε)n edges contains a directed path of lengthcn. This settles a conjecture of Erdõs.     

The strongest monotone degree condition for n-connectedness of a graph

It is shown that Bondy's degree condition for n-connectedness of a graph is the strongest monotone degree condition for forcibly n-connected graphic sequences.     

Matroids,generalized networks,and electric network synthesis

Matroid theory has been applied to solve problems in generalized assignment, operations research, control theory, network theory, flow theory, generalized flow theory or linear programming, coding theory, and telecommunication network design. The operations of matroid union, matroid partitioning, matroid intersection, and the theorem on the greedy algorithm, Rado's theorem, and Brualdi's symmetric version of Rado's theorem have been important for some of these applications. In this paper we consider the application of matroids to solve problems in network synthesis. Previously Bruno and Weinberg defined a generalized network, which is a network based on a matroid rather than a graph; for a generalized network the duality principle holds whereas it does not hold for a network based on a graph. We use the concept of the generalized network to formulate a solution to the following problem: What are the necessary and sufficient conditions for a singular matrix of real numbers, of order p and rank s, to be realizable as the open-circuit resistance matrix of a resistance p-port network. A simple algorithm is given for carriyng out the synthesis. We then present a number of unsolved problems, included among which is what could be called the four-color problem of network synthesis, namely, the resistance n-port problem.     

Hamiltonian paths in oriented graphs

A short proof is given of Meyniel's theorem on Hamiltonian cycles in oriented graphs. Analogous conditions are obtained for a graph to be Hamiltonianconnected.     

Kneser's conjecture,chromatic number,and homotopy

If the simplicial complex formed by the neighborhoods of points of a graph is (k ? 2)-connected then the graph is not k-colorable. As a corollary Kneser's conjecture is proved, asserting that if all n-subsets of a (2n ? k)-element set are divided into k + 1 classes, one of the classes contains two disjoint n-subsets.     

The 1-width of (0,1)-matrices having constant row sum 3

In this note we establish upper bounds for the 1-width of an m × n matrix of 0's and 1's having three 1's in every row and having a constant number, c, of 1's in every column. When c = 3, this upper bound is $\text{n}\text{2}$ and when c = 4 this estimate is $\text{5n}\text{9}$. In these cases the upper bound is best possible, in the sense that for every possible size there exist matrices with this maximal 1-width. The technique of proof is also used to improve the known bound for the 1-width of (0, 1)-matrices with constant line sum 4.