On dimensional rigidity of bar-and-joint frameworks

Let V={1,2,…,n}. A mapping p:V→R^r, where p¹,…,pⁿ are not contained in a proper hyper-plane is called an r-configuration. Let G=(V,E) be a simple connected graph on n vertices. Then an r-configuration p together with graph G, where adjacent vertices of G are constrained to stay the same distance apart, is called a bar-and-joint framework (or a framework) in R^r, and is denoted by G(p). In this paper we introduce the notion of dimensional rigidity of frameworks, and we study the problem of determining whether or not a given G(p) is dimensionally rigid. A given framework G(p) in R^r is said to be dimensionally rigid iff there does not exist a framework G(q) in R^s for s?r+1, such that ∥qⁱ-q^j∥²=∥pⁱ-p^j∥² for all (i,j)∈E. We present necessary and sufficient conditions for G(p) to be dimensionally rigid, and we formulate the problem of checking the validity of these conditions as a semidefinite programming (SDP) problem. The case where the points p¹,…,pⁿ of the given r-configuration are in general position, is also investigated.     

On the rigidity of molecular graphs

The rigidity of squares of graphs in three-space has important applications to the study of flexibility in molecules. The Molecular Conjecture, posed in 1984 by T.-S. Tay and W. Whiteley, states that the square G ² of a graph G of minimum degree at least two is rigid if and only if G has six spanning trees which cover each edge of G at most five times. We give a lower bound on the degrees of freedom of G ² in terms of forest covers of G. This provides a self-contained proof that the existence of the above six spanning trees is a necessary condition for the rigidity of G ². In addition, we prove that the truth of the Molecular Conjecture would imply that our lower bound is tight, and would also imply that a conjecture of Jacobs on ‘independent’ squares is valid. This work was supported by an International Joint Project grant from the Royal Society. Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization and the Hungarian Scientific Research Fund grant no. T049671, T60802.     

On a geometric property of perfect graphs

LetG be a graph,VP(G) its vertex packing polytope and letA(G) be obtained by reflectingVP(G) in all Cartersian coordinates. Denoting byA*(G) the set obtained similarly from the fractional vertex packing polytope, we prove that the segment connecting any two non-antipodal vertices ofA(G) is contained in the surface ofA(G) and thatG is perfect if and only ifA*(G) has a similar property.     

Infinite highly arc transitive digraphs and universal covering digraphs

A digraph (that is a directed graph) is said to be highly arc transitive if its automorphism group is transitive on the set ofs-arcs for eachs0. Several new constructions are given of infinite highly arc transitive digraphs. In particular, for a connected, 1-arc transitive, bipartite digraph, a highly arc transitive digraphDL() is constructed and is shown to be a covering digraph for every digraph in a certain classD() of connected digraphs. Moreover, if is locally finite, thenDL() is a universal covering digraph forD(). Further constructions of infinite highly arc transitive digraphs are given.The second author wishes to acknowledge the hospitality of the Mathematical Institute of the University of Oxford, and the University of Auckland, during the period when the research for this paper was doneResearch supported by the Australian Research Council     

A characterization of affine cylinders

A class of non-metrizable connections is studied. It contains the only non-flat locally symmetric connections existing on affine hypersurfaces of type number 1.The research was supported by the Alexander von Humboldt Stiftung and by the KBN grant no 2 P301 03004.     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

The Topological Tverberg Theorem and winding numbers

The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d?1, and if q is a prime power, but not yet in general.)The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a “Winding Number Conjecture” that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to R^d. “Many Tverberg partitions” arise if and only if there are “many q-winding partitions.”The d=2 case of the Winding Number Conjecture is a problem about drawings of the complete graphs K_3q-2 in the plane. We investigate graphs that are minimal with respect to the winding number condition.     

The perfectly Matchable Subgraph Polytope of an arbitrary graph

The Perfectly Matchable Subgraph Polytope of a graphG=(V, E), denoted byPMS(G), is the convex hull of the incidence vectors of thoseXV which induce a subgraph having a perfect matching. We describe a linear system whose solution set isPMS(G), for a general (nonbipartite) graphG. We show how it can be derived via a projection technique from Edmonds' characterization of the matching polytope ofG. We also show that this system can be deduced from the earlier bipartite case [2], by using the Edmonds-Gallai structure theorem. Finally, we characterize which inequalities are facet inducing forPMS(G), and hence essential.     

On the full automorphism group of a graph

While it is easy to characterize the graphs on which a given transitive permutation groupG acts, it is very difficult to characterize the graphsX with Aut (X)=G. We prove here that for the certain transitive permutation groups a simple necessary condition is also sufficient. As a corollary we find that, whenG is ap-group with no homomorphism ontoZ _p wrZ _p , almost all Cayley graphs ofG have automorphism group isomorphic toG.     

Hypothesis testing using affine linear estimators

The general linear hypothesis is usually tested by means of anF-statistic dependent on the least squares estimator. In this paper, a class of linear estimators is identified which can also serve as a basis for such anF-statistic. Conditions are derived under which thisF-statistic coincides with the usual one. This opens the possibility of constructing minimax-estimators which dominate LS with respect to risk, yielding the same test results.Support by Deutsche Forschungsgemeinschaft, Grant No. Tr 253/1-2 is gratefully acknowledged.     

Crystallographic reptiles

We consider tilings ofR ⁿ by copies of a compact setA under the action of a crystallographic group, such that the union ofk suitably chosen tiles is affinely isomorphic toA. For dimensionn=2 we show that for eachk2 there is a finite number of isomorphy classes of such setsA which are homeomorphic to a disk. We give an algorithm which determines all disk-like tiles for a given group and numberk. The algorithm will be applied to the groupsp2 andp3 withk=3.     

Cones of alternating and cut submodular set functions

We describe facets of the cones of alternating set functions and cut submodular set functions generated by directed and undirected graphs and by uniform even hypergraphs. This answers a question asked by L. Lovász at the Bonn Mathematical Programming Conference in 1982. We show that there is a network flow algorithm for minimizing a hypergraph cut set function.     

On a Heilbronn-type problem

Let F be a convex figure with area |F| and let G(n,F) denote the smallest number such that from any n points of F we can get G(n,F) triangles with areas less than or equal to |F|/4. In this article, to generalize some results of Soifer, we will prove that for any triangle T, G(5,T)=3; for any parallelogram P, G(5,P)=2; for any convex figure F, if S(F)=6, then G(6,F)=4.     

The graph induced by affine <Emphasis Type="Italic">M</Emphasis>-flats over finite fields II

Let AG(n, F _q) be the n-dimensional affine space over F _q, where F _q is a finite field with q elements. Denote by Γ ^(m) the graph induced by m-flats of AG(n, F _q). For any two adjacent vertices E and F of is studied. In particular, sizes of maximal cliques in Γ ^(m) are determined and it is shown that Γ ^(m) is not edge-regular when m<n−1. Supported by the National Natural Science Foundation of China (19571024) and Hunan Provincial Department of Education (02C512).     

On automorphisms of infinite graphs with forbidden subgraphs

LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2).     

Best affine unbiased representations of the fully restricted general Gauss-Markov model

This article completes and simplifies earlier results on the derivation of best linear, or affine, unbiased estimates in the general Gauss-Markov model with a singular dispersion matrix and additional restrictions under very general conditions. We provide the class of all linear representations of the best affine unbiased estimator with precise statements concerning its indeterminacy.     

Weak and universal consistency of moving weighted averages

The properties of weighted averages as linear estimators of a regression function and its derivatives are investigated for the fixed design case. Results on weak consistency and on universal consistency are derived, using a modification of the definition of Stone [10]. As examples we consider kernel estimates and weighted local regression estimators and show that the general results apply.     

Puzzles and polytope isomorphisms

We show that an isomorphism between the graphs of two simple polytopes of arbitrary dimension can always be extended to an isomorphism between the polytopes themselves. It has been convenient to study the dual situation, involving what we like to call the puzzle of a simplicial polytope.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday.     

Pairs of edge-disjoint Hamiltonian circuits

Aequationes mathematicae -     

ON CIRCULANT DIGRAPHS WITH REGULAR AUTOMORPHISM GROUPS

Abstract. We prove that the cyclic group Zn(n≥3) has a k-regular digraph regular