Hadwiger's conjecture forK 6-free graphs

In 1943, Hadwiger made the conjecture that every loopless graph not contractible to the complete graph ont+1 vertices ist-colourable. Whent3 this is easy, and whent=4, Wagner's theorem of 1937 shows the conjecture to be equivalent to the four-colour conjecture (the 4CC). However, whent5 it has remained open. Here we show that whent=5 it is also equivalent to the 4CC. More precisely, we show (without assuming the 4CC) that every minimal counterexample to Hadwiger's conjecture whent=5 is apex, that is, it consists of a planar graph with one additional vertex. Consequently, the 4CC implies Hadwiger's conjecture whent=5, because it implies that apex graphs are 5-colourable.Research partially supported by NSF grants number DMS 8903132, and DMS 9103480 respectively. Both authors were also partially supported by the DIMACS Center at Rutgers University, and the research was carried out partially under a consulting agreement with Bellcore.     

Near-perfect matrices

A 0, 1 matrixA isnear-perfect if the integer hull of the polyhedron {x0: Ax } can be obtained by adding one extra (rank) constraint. We show that in general, such matrices arise as the cliquenode incidence matrices of graphs. We give a colouring-like characterization of the corresponding class of near-perfect graphs which shows that one need only check integrality of a certain linear program for each 0, 1, 2-valued objective function. This in contrast with perfect matrices where it is sufficient to check 0, 1-valued objective functions. We also make the following conjecture: a graph is near-perfect if and only if sequentially lifting any rank inequality associated with a minimally imperfect graph results in the rank inequality for the whole graph. We show that the conjecture is implied by the Strong Perfect Graph Conjecture. (It is also shown to hold for graphs with no stable set of size eleven.) Our results are used to strengthen (and give a new proof of) a theorem of Padberg. This results in a new characterization of minimally imperfect graphs: a graph is minimally imperfect if and only if both the graph and its complement are near-perfect.The research has partially been done when the author visited Mathematic Centrum, CWI, Amsterdam, The Netherlands.     

A note on the split rank of intersection cuts

In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that élog₂ (l)ù{\lceil \log_2 (l)\rceil} is a lower bound on the split rank of the intersection cut, where l is the number of integer points lying on the boundary of the restricted lattice-free set satisfying the condition that no two points lie on the same facet of the restricted lattice-free set. The use of this result is illustrated by obtaining a lower bound of élog₂( n+1) ù{\lceil \log_2( n+1) \rceil} on the split rank of n-row mixing inequalities.     

On the intersection of subgroups of a free group

Summary The Hanna Neumann Conjecture says that the intersection of subgroups of rankn+1 andm+1 of a free group has rank at mostnm+1. This paper proves the conjecture for the casem=1. (See Theorem 1.) Our methods imply that the strengthened Hanna Neumann Conjecture is also true in this case (Theorem 2).Oblatum 31-V-1991 & 8-X-1991     

Subgroups of Free Groups: a Contribution to the Hanna Neumann Conjecture

We prove that the strengthened Hanna Neumann conjecture, on the rank of the inter-section of finitely generated subgroups of a free group, holds for a large class of groups characterized by geometric properties. One particular case of our result implies that the conjecture holds for all positively finitely generated subgroups of the free group F(A) (over the basis A), that is, for subgroups which admit a finite set of generators taken in the free monoid over A.     

Equivalence of the strengthened Hanna Neumann conjecture and the amalgamated graph conjecture

Summary We show that Walter Neumann's strengthened form of Hanna Neumann's conjecture on the best possible upper bound for the rank of the intersection of two subgroups of a free group is equivalent to a conjecture on the best possible upper bound for the number of edges in a bipartite graph with a certain weak symmetry condition. We illustrate the usefulness of this equivalence by deriving relatively easily certain previously known results.Oblatum 30-VIII-1993     

Vertex-Compressed Subalgebras of a Graph von Neumann Algebra

In Cho (Acta Appl. Math. 95:95–134, 2007 and Complex Anal. Oper. Theory 1:367–398, 2007), we introduced Graph von Neumann Algebras which are the (groupoid) crossed product algebras of von Neumann algebras and graph groupoids via graph-representations, which are groupoid actions. In Cho (Acta Appl. Math. 95:95–134, 2007), we showed that such crossed product algebras have the amalgamated reduced free probabilistic properties, where the reduction is totally depending on given directed graphs. Moreover, in Cho (Complex Anal. Oper. Theory 1:367–398, 2007), we characterize each amalgamated free blocks of graph von Neumann algebras: we showed that they are characterized by the well-known von Neumann algebras: Classical group crossed product algebras and (operator-valued) matricial algebras. This shows that we can provide a nicer way to investigate such groupoid crossed product algebras, since we only need to concentrate on studying graph groupoids and characterized algebras. How about the compressed subalgebras of them? i.e., how about the inner (cornered) structures of a graph von Neumann algebra? In this paper, we will provides the answer of this question. Consequently, we show that vertex-compressed subalgebras of a graph von Neumann algebra are characterized by other graph von Neumann algebras. This gives the full characterization of the vertex-compressed subalgebras of a graph von Neumann algebra, by other graph von Neumann algebras.     

On 3-pushdown graphs with large separators

For an integers letl ^s (n), thes-iterated logarithm function, be defined inductively:l ⁰ (n)=n,l ^s+1 (n)=log₂ (l ² (n)) fors0. We show that for every fixeds and alln large enough, there is ann-vertex 3-pushdown graph whose smallest separator contains at least(n/l ^s (n)) vertices.The work of the first author was supported in part by NSF Grants MCS-83-03139, DCR-85-11713 and CCR-86-05353.The work of the second author was supported in part by NSF Grants MCS-84-16190.     

Bidegree of graph and degeneracy number

The bidegree (G) of a graph G is the minimum of the sum of the degrees of any two subgraphs covering all vertices of G. A close connection of the bidegree with the degeneracy of the complementary graph of G is found. Sharp double- sided bounds of the Nordhaus- Gaddum class for the degeneracy number are obtained. This enables the author to give upper and lower bounds for max{(G)+(¯G)},within the class of n-vertex graphs G such that the gap between the two bounds is less than or equal to 3. As a corollary, a conjecture of Catlin (1976) on the behavior of (G)+(¯G) is refuted.Translated from Matematicheskie Zametki, Vol. 53, No. 4, pp. 13–20, April, 1993.     

The Coherence of One-Relator Groups with Torsion and the Hanna Neumann Conjecture

A conjecture is proposed, bounding the number of cycles withlabel Wⁿ in a labeled directed graph. Some partial results towardsthis conjecture are established. As a consequence, it is provedthat a₁, a₂,...|Wⁿ is coherent for n 4. Furthermore, it iscoherent for n 2, provided that the strengthened Hanna Neumannconjecture holds. 2000 Mathematics Subject Classification 20F06,05C38.     

Absolute continuity of convolutions of orbital measures on Riemannian symmetric spaces

We study the absolute continuity of the measures and of on the Riemannian symmetric spaces X of noncompact type for nonzero elements Xj, X∈a. For m,l?r+1, where r is the rank of X, the considered convolutions have a density. We conjecture that the condition m,l?r+1 is necessary. The conjecture is proved for the symmetric spaces of type An−1. Moreover, the minimal value of l is determined, in function of the irregularity of X.     

On the structure of graphs with a unique k‐factor

In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000     

The Hankel pencil conjecture

The Toeplitz pencil conjecture stated in [W. Schmale, P.K. Sharma, Problem 30-3: singularity of a toeplitz matrix, IMAGE 30 (2003); W. Schmale, P.K. Sharma, Cyclizable matrix pairs over and a conjecture on toeplitz pencils, Linear Algebra Appl. 389 (2004) 33-42] is equivalent to a conjecture for n×n Hankel pencils of the form H_n(x)=(c_i+j-n+1), where c₀=x is an indeterminate, c_l=0 for l<0, and for l1. In this paper it is shown to be implied by another conjecture, which we call the root conjecture. The root conjecture asserts a strong relationship between the roots of certain submaximal minors of H_n(x) specialized to have c₁=c₂=1. We give explicit formulae in the c_i for these minors and prove the root conjecture for minors m_nn,m_n-1,n of degree 6. This implies the Hankel Pencil conjecture for matrices up to size 8×8. The main tools involved are a partial parametrization of the set of solutions of systems of polynomial equations that are both homogeneous and index sum homogeneous, and use of the Sylvester identity for matrices.     

Matchings and independent sets of a fixed size in regular graphs

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size ℓ in a d-regular graph on N vertices. For bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size ℓ in the graph consisting of disjoint copies of K_d,d. This provides asymptotic evidence for a conjecture of S. Friedland et al. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.     

Transitive Edge Coloring of Graphs and Dimension of Lattices

We explore properties of edge colorings of graphs dened by set intersections. An edge coloring of a graph G with vertex set V ={1,2, . . . , n} is called transitive if one can associate sets F ₁,F ₂, . . .,F _n to vertices of G so that for any two edges ij,kl E(G), the color of ij and kl is the same if and only if F _i F _j = F _k F _l . The term transitive refers to a natural partial order on the color set of these colorings.We prove a canonical Ramsey type result for transitive colorings of complete graphs which is equivalent to a stronger form of a conjecture of A. Sali on hypergraphs. This—through the reduction of Sali—shows that the dimension of n-element lattices is o(n) as conjectured by Füredi and Kahn.The proof relies on concepts and results which seem to have independent interest. One of them is a generalization of the induced matching lemma of Ruzsa and Szemerédi for transitive colorings. * Research supported in part by OTKA Grant T029074.     

Radicals coinciding with the von Neumann regular radical on artinian rings

We study radicals which coincide on artinian rings with Jacobson semisimple rings or equivalently with von Neumann regular rings. Exact lower and upper bounds for strong coincidence are given. For weak coincidence the exact lower bound is that for strong coincidence. We determine the smallest homomorphically closed class which contains all radicals coinciding in the weak sense with the von Neumann regular radical on artinian rings, but we do not know even the existence of the upper bound for weak coincidence. If a radical coincides with the von Neumann regular radical on artinian rings in the strong sense, then (A) is a direct summand inA for every aritian ringA.Research carried out within the Austro-Hungarian Bilateral Intergovernmental Cooperation Program A-31. Research partially supported by Hungarian National Foundations for Scientific Research Grant No. T4265The second author gratefully acknowledges the support of the Carnegie Trust for Universities of Scotland     

Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs

We prove the nonexistence of a distance-regular graph with intersection array {74,54,15;1,9,60} and of distance-regular graphs with intersection arrays

{4r³+8r²+6r+1,2r(r+1)(2r+1),2r²+2r+1;1,2r(r+1),(2r+1)(2r²+2r+1)}