Parabolic rectangle packings

The contacts graph (or nerve) of a packing is a combinatorial graph which describes the combinatorics of the packing. Let G be the 1-skeleton of a triangulation of an open disk and let P be a rectangle packing with contact graph G. In this paper a topological criterion for deciding whether G is an α-EL parabolic graph is given. Our result shows the internal relation between the topological property of the packing P and the combinatorial property of the contacts graph G of P.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

Greatest common subgraphs with specified properties

A graphG without isolated vertices is a greatest common subgraph of a setG of graphs, all having the same size, ifG is a graph of maximum size that is isomorphic to a subgraph of every graph inG. A number of results concerning greatest common subgraphs are presented. For several graphical propertiesP, we discuss the problem of determining, for a given graphG with propertyP, the existence of two non-isomorphic graphsG ₁ andG ₂ of equal size, also with propertyP, such thatG is the unique greatest common subgraph ofG ₁ andG ₂. In particular, this problem is solved whenP is the property of being 2-connected and whenP is the property of having chromatic numbern.     

The Dirichlet problem at infinity for random walks on graphs with a strong isoperimetric inequality

Summary We study the spatial behaviour of random walks on infinite graphs which are not necessarily invariant under some transitive group action and whose transition probabilities may have infinite range. We assume that the underlying graphG satisfies a strong isoperimetric inequality and that the transition operatorP is strongly reversible, uniformly irreducible and satisfies a uniform first moment condition. We prove that under these hypotheses the random walk converges almost surely to a random end ofG and that the Dirichlet problem forP-harmonic functions is solvable with respect to the end compactification If in addition the graph as a metric space is hyperbolic in the sense of Gromov, then the same conclusions also hold for the hyperbolic compactification in the place of the end compactification. The main tool is the exponential decay of the transition probabilities implied by the strong isoperimetric inequality. Finally, it is shown how the same technique can be applied to Brownian motion to obtain analogous results for Riemannian manifolds satisfying Cheeger's isoperimetric inequality. In particular, in this general context new (and simpler) proofs of well known results on the Dirichlet problem for negatively curved manifolds are obtained.The first author was partially supported by Consiglio Nazionale delle Ricerche, GNAFA Current address: Department of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, Scotland     

The maximal number of inducedr-partite subgraphs

In this paper, we extend earlier results concerning the maximal number of induced completer-partite graphs in a graphG of ordern. In particular, we show that ift > 1 + logr, then the maximal number of inducedK _r (t)'s is achieved in the case of the Turán graphT _r (n), and that this bound ont is essentially best possible.     

Clique covering of graphs

Let cc(G) denote the least number of complete subgraphs necessary to cover the edges of a graphG. Erd?s conjectured that for a graphG onn vertices $$cc(G) + cc(\bar G) \leqq \frac{1}{4}n^2 + 2$$ ifn is sufficiently large. We prove this conjecture.     

Extensions on 2-edge connected 3-regular up-embeddable graphs

1.IntroductionLetHbea3-regulargraph.Forel,e2,e3EE(H)(el,eZande3areallowedtobethesame),weaddthreenewvenicesal)wZandw3inel,eZande3respectively.ChoosingueV(H),andthenjoiningutofi(i=1,2,3),weatlastobtaina3-regulargraphG.Or,inotherwords,wesaythatGisobtainedfromHbyanM-extension.DenoteG=M(u)(H)(seeFig.1).LetHbea3-regulargraph.Takingel,eZEE(H)(elandeZareallowedtobethesame),weputtwodistinctvenicestvian0dwZinelandeZrespectively,andaddtwodistinctvenicesu,v4V(H),thenjoinutoal,joinvtowZandjoin…     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

A new characterization of frobenius complements

LetH, G be finite groups such thatH acts onG and each non-trivial element ofH fixes at mostf elements ofG. It is shown that, ifG is sufficiently large, thenH has the structure of a Frobenius complement. This result depends on the classification of finite simple groups. We conclude that, ifG is a finite group andA ⊆G is any non-cyclic abelian subgroup, then the order ofG is bounded above in terms of the maximal order of a centralizerC _G(a) for 1≠a ∈A.     

Coloring infinite graphs and the Boolean prime ideal theorem

It is shown that the following theorem holds in set theory without AC: There is a functionG which assigns to each Boolean algebraB a graphG(B) such that (1) ifG(B) is 3-colorable then there is a prime ideal inB and (2) every finite subgraph ofG(B) is 3-colorable. The proof uses a combinatorial lemma on finite graphs.     

Crossed products over prime rings

In this paper we obtain necessary and sufficient conditions for the crossed productR *G to be prime or semiprime under the assumption thatR is prime. The main techniques used are the Δ-methods which reduce these questions to the finite normal subgroups ofG and a study of theX-inner automorphisms ofR which enables us to handle these finite groups. In particular we show thatR *G is semiprime ifR has characteristic 0. Furthermore, ifR has characteristicp>0, thenR *G is semiprime if and only ifR *P is semiprime for all elementary abelianp-subgroupsP of Δ⁺(G) ∩G _inn.     

An extension of the könig-egerváry property to node-weighted bidirected graphs

Given a bidirected graphG and a vectorb of positive integral node-weights, an integer linear program IP is defined on (G, b). IP generalizes the node packing problem on a node-weighted (undirected) graph in the sense that it reduces to the latter whenG is undirected. A polynomial time algorithm is given that recognizes whether CP (the linear program obtained by relaxing the integrality constraints of IP) has an integral optimal solution. Also an efficient method for solving the linear programming dual of CP is described.Supported by the Natural Sciences and Engineering Research Council of Canada.     

On the Probabilistic Zeta Function for Finite Groups

LetGbe a finite group, and define the function[formula]where μ is the Möbius function on the subgroup lattice ofG. The functionP(G, s) is the multiplicative inverse of a zeta function forG, as described by Mann and Boston. Boston conjectured thatP′(G, 1) = 0 ifGis a nonabelian simple. We will prove a generalization of this conjecture, showing thatP′(G, 1) = 0 unlessG/O_p(G) is cyclic for some primep.     

Sylow normalizers and character tables, II

Suppose thatG is a finitep-solvable group and letPε Syl _p (G). In this note, we prove that the character table ofG determines ifN _G(itP)/P is abelian. Research partially supported by DGICYT.     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Greatest common divisors and least common multiples of graphs

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG ₁ andG ₂ ifG is a graph of maximum size for whichG|G ₁ andG|G ₂, while a graphH without isolated vertices is a least common multiple ofG ₁ andG ₂ ifH is a graph of minimum size for whichG ₁|H andG ₂|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG ₁ andG ₂ to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG ₁,G ₂ of graphs are determined, including when one ofG ₁ andG ₂ is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060     

Another family of chromatically unique graphs

LetP(G; ) denote the chromatic polynomial of a graphG, expressed in the variable. ThenG is said to be chromatically unique ifG is isomorphic withH for any graphH such thatP(H; ) = P(G; ). In this paper, we provide a new family of chromatically unique graphs.Research was partly supported by the University of Agriculture research grant # 50205-91-05     

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.     

A characterization of the Cauchy-type distributions on boundaries of semisimple groups

We give here a characterization of the Cauchy-type distributions onG/P, whereG is a semisimple Lie group andP is a parabolic subgroup.     

A classification of parabolic subgroups of classical groups with a finite number of orbits on the unipotent radical

LetG be a classical algebraic group defined over an algebraically closed field. We classify all instances when a parabolic subgroupP ofG acts on its unipotent radicalP _u , or onp _u , the Lie algebra ofP _u , with only a finite number of orbits.The proof proceeds in two parts. First we obtain a reduction to the case of general linear groups. In a second step, a solution for these is achieved by studying the representation theory of a particular quiver with certain relations.Furthermore, for general linear groups we obtain a combinatorial formula for the number of orbits in the finite cases.