A condition for matchability in hypergraphs

An extension of Hall's theorem is proved, which gives a condition for complete matchings in a certain class of hypergraphs.Research partially supported by NSERC.     

On an application of Hall's representatives theorem to a finite geometry problem

It is well-known thatn points not belonging to a hyperplane determine at leastn hyperplanes. The possible configurations of hyperplanes in the case when the number of hyperplanes is equal ton are known, too. In this paper we obtain these results by means of Hall's representatives theorem. The setting is that of a finite geometry.     

HYPERFINITE TRANSVERSAL THEORY. II

We continue the investigation of validity of Hall's theorem in the case of the Loeb space of an internal, uniformly distributed, hyperfinite measure space initiated in1992 by the author. Some new classes of graphs are introduced for which the measure theoretic version of Hall's theorem still holds.

     

A graphic construction of the collection formula for certain types of groups

Procedures for calculating P. Hall's famous collection formula for metabelian and two types of transmetabelian groups are described. Complicated combinatorial calculations are based on graphs corresponding to basic monomials. In conclusion programs written in PASCAL are given.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademiya Nauk SSSR, Vol. 191, pp. 140–151, 1991.     

若干家族p-群的自同构群的阶

本文确定了Rodney James文章中P．Hall isoclinism族第一家族到第十家族所有群的自同构群的阶,并纠正了Rodney James文章里的某些错误．     

A Tree Version of Kőnig's Theorem

Kőnig's theorem states that the covering number and the matching number of a bipartite graph are equal. We prove a generalization, in which the point in one fixed side of the graph of each edge is replaced by a subtree of a given tree. The proof uses a recent extension of Hall's theorem to families of hypergraphs, by the first author and P. Haxell [2]. As an application we prove a special case (that of chordal graphs) of a conjecture of B. Reed. Received January 27, 2000/Revised November 2, 2000 RID=" " ID=" " The research of the first author was supported by grants from the Israel Science Foundation, the M. & M.L Bank Mathematics Research Fund and the fund for the promotion of research at the Technion.     

Asymptotic expansions of the distributions of estimators in canonical correlation analysis under nonnormality

Asymptotic expansions of the distributions of typical estimators in canonical correlation analysis under nonnormality are obtained. The expansions include the Edgeworth expansions up to order O(1/n) for the parameter estimators standardized by the population standard errors, and the corresponding expansion by Hall's method with variable transformation. The expansions for the Studentized estimators are also given using the Cornish-Fisher expansion and Hall's method. The parameter estimators are dealt with in the context of estimation for the covariance structure in canonical correlation analysis. The distributions of the associated statistics (the structure of the canonical variables, the scaled log likelihood ratio and Rozeboom's between-set correlation) are also expanded. The robustness of the normal-theory asymptotic variances of the sample canonical correlations and associated statistics are shown when a latent variable model holds. Simulations are performed to see the accuracy of the asymptotic results in finite samples.     

图论中若干重要定理的历史注记

考察了图论中若干重要定理的历史背景,这些定理包括图论基本定理,矩阵-树定理,门格尔定理,霍尔定理,柯尼希定理,塔特定理,彼得森定理,库拉托夫斯基定理,布鲁克斯定理和维津定理.     

A collection formula

A table of partially ordered sets, corresponding to the basis commutators (in Hall's sense) of weight 9, is given. On the basis of this table, the exponents in the collection formula can be found by elementary combinatorial methods. An example is given.Translated from Zapiski Nauchnykh Seminarov Leningardskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 46, pp. 59–63, 1974.     

Jacobi identity and P. Hall's collection formula in two types of transmetabelian groups

The Jacobi identity and Hall's collection formula are derived for groups that generalize metabelian groups in two different ways: 1) the third term of the lower central series is abelian, and 2) the commutator subgroup is of nilpotency class 2.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A Steklova Akademii Nauk SSSR, Vol. 175, pp. 106–112, 1989.     

Perfect matchings in balanced hypergraphs

We generalize Hall's condition for the existence of a perfect matching in a bipartite graph, to balanced hypergraphs.This work was partially supported in part by NSF grants DMI-9424348, DMS-9509581 and ONR grant N00014-89-J-1063. Ajai Kapoor was also supported by a grant from Gruppo Nazionale Delle Riccerche-CNR. Finally, we acknowledge the support of Laboratiore ARTEMIS, Université Joseph Fourier, Grenoble.     

Perfect Matchings in Balanced Hypergraphs – A Combinatorial Approach

Our topic is an extension of the following classical result of Hall to hypergraphs: A bipartite graph G contains a perfect matching if and only if for each independent set X of vertices, at least |X| vertices of G are adjacent to some vertex of X. Berge generalized the concept of bipartite graphs to hypergraphs by defining a hypergraph G to be balanced if each odd cycle in G has an edge containing at least three vertices of the cycle. Based on this concept, Conforti, Cornuéjols, Kapoor, and Vušković extended Hall's result by proving that a balanced hypergraph G contains a perfect matching if and only if for any disjoint sets A and B of vertices with |A| > |B|, there is an edge in G containing more vertices in A than in B (for graphs, the latter condition is equivalent to the latter one in Hall's result). Their proof is non-combinatorial and highly based on the theory of linear programming. In the present paper, we give an elementary combinatorial proof. Received April 29, 1997     

Bases of free metabelian and transmetabelian groups

A definition of the basis of a group written in additive form is given based on P. Hall's collecting process. The bases of free rank 2 groups of the following three types are found: metabelian, transmetabelian of the first type (with an Abelian third term in the lower central series), and transmetabelian of the second type (the nilpotency class of whose derived group is equal to two).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademiya Nauk SSSR, Vol. 191, pp. 126–139, 1991.     

Closed curves and geodesics with two self-intersections on the Punctured torus

We classify the free homotopy classes of closed curves with minimal self intersection number two on a once punctured torus,T, up to homeomorphism. Of these, there are six primitive classes and two imprimitive. The classification leads to the topological result that, up to homeomorphism, there is a unique curve in each class realizing the minimum self intersection number. The classification yields a complete classification of geodesics on hyperbolicT which have self intersection number two. We also derive new results on the Markoff spectrum of diophantine approximation; in particular, exactly three of the imprimitive classes correspond to families of Markoff values below Hall's ray.Research started during the Summer 1994 NSF REU Program at Oregon State University and partially supported by NSF DMS 9300281     

幂零Hall π-子群的存在性

本文首先将Ｈａｌ定理推广为：设Ｎ为Ｇ的正规子群，若Ｎ为Ｅｎπ群，Ｇ／Ｎ为Ｄπ群，则Ｇ为Ｄπ群．在此基础上得到了群Ｇ为Ｅｎπ群的充要条件为：（１）Ｇ存在正规子群Ｎ，满足Ｎ及Ｇ／Ｎ为Ｅｎπ群；（２）对任意ｐ∈π，任意ｑ∈π ｛ｐ｝及任意ｐ 元素ｘ，ＣＧ（ｘ）含Ｇ的Ｓｙｌｏｗｑ 子群．另外，我们对非Ａｂｌｅ单群的情形也进行了一些讨论．     

Infinite Matroidal Version of Hall's Matching Theorem

Hall's theorem for bipartite graphs gives a necessary and sufficientcondition for the existence of a matching in a given bipartitegraph. Aharoni and Ziv have generalized the notion of matchabilityto a pair of possibly infinite matroids on the same set andgiven a condition that is sufficient for the matchability ofa given pair (M, W) of finitary matroids, where the matroidM is SCF (a sum of countably many matroids of finite rank).The condition of Aharoni and Ziv is not necessary for matchability.The paper gives a condition that is necessary for the existenceof a matching for any pair of matroids (not necessarily finitary)and is sufficient for any pair (M, W) of finitary matroids,where the matroid M is SCF.     

Triangulated Spheres and Colored Cliques

Abstract. In [1] a generalization of Hall's theorem was proved for families of hypergraphs. The proof used Sperner's lemma. In [5] Meshulam proved an extension of this result, using homology and the nerve theorem. In this paper we show how the triangulations method can be used to derive Meshulam's results. As in [1], the proof is based on results on extensions of triangulations from the sphere to the full ball. A typical result of this type is that any triangulation of the (d-1) -dimensional sphere S ^d-1 can be extended to a triangulation of the ball B ^d , by adding one point at a time, having degree at most 2d to its predecessors.     

Triangulated Spheres and Colored Cliques

   Abstract. In [1] a generalization of Hall's theorem was proved for families of hypergraphs. The proof used Sperner's lemma. In [5] Meshulam proved an extension of this result, using homology and the nerve theorem. In this paper we show how the triangulations method can be used to derive Meshulam's results. As in [1], the proof is based on results on extensions of triangulations from the sphere to the full ball. A typical result of this type is that any triangulation of the (d-1) -dimensional sphere S ^d-1 can be extended to a triangulation of the ball B ^d , by adding one point at a time, having degree at most 2d to its predecessors.     

On the Parametrization of the Afocal Stable Distributions

Thanks to Hall's documentation of a situation he described asa ‘Comedy of errors’ in the earlier literature onstable distributions, there is now general agreement as to theparametrization of these distributions when standardized asto location and scale. However, two subtly different parametrizationsof location and scale remain current in the afocal stable cases,defined as those with characteristic exponent = 1 and skewnessparameter ß 0. The more widely used parametrization,adopted by Hall and two recent monographs, lacks the linearityproperty that is ordinarily expected of location and scale parameters.This note shows that the alternative parametrization has thislinearity property, and compares the implications of the twoparametrizations for properties of stable distributions. A thirdrecent monograph seeks to avoid these issues by denying thatthe afocal stable distributions are stable at all, but it isshown that they are, in fact, integral members of the stablefamily.     

3-Class Association Schemes and Hadamard Matrices of a Certain Block Form

In this paper all the so-called checkered Hadamard matrices of order 16 are determined (i.e., Hadamard matrices consisting of 16 square blocksH_ijof order 4 such thatH_ii = J₄andH_ijJ₄ = J₄H_ij = 0 fori≠jand whereJ₄is the all-one matrix of order 4). It is shown that the checkered Hadamard matrices of order 16 all belong to one of the Hall's classes I, II or III. Moreover the so-called block equivalency classes are determined.