Crossing numbers of sequences of graphs II: Planar tiles

We describe a method of creating an infinite family of crossing‐critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k‐crossing‐critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k‐crossing‐critical graphs all having average degree r. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332–341, 2003     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

Expected Reflection Distance in G(r, 1, n) after a Fixed Number of Reflections

Extending to r > 1 a formula of the authors, we compute the expected reflection distance of a product of t random reflections in the complex reflection group G(r, 1, n). The result relies on an explicit decomposition of the reflection distance function into irreducible G(r, 1, n)-characters and on the eigenvalues of certain adjacency matrices.Received December 8, 2003     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

Normal growth of large groups

For a finitely generated group $\Gamma$, denote by the number of normal subgroups of index n. A. Lubotzky proved that for the free group F_r of rank r, is of type n^logn. We show that the same is true for a much larger class of groups. On the other hand we show that for almost all n, the inequality < holds true for every r-generated group $\Gamma$.Received: 30 October 2002     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

A Bose‐Burton type theorem for quadrics

Let Q be a non‐degenerate quadric defined by a quadratic form in the finite projective space PG(d,q). Let r be the dimension of the generators of Q. For all k with 2 ≤ k < r we determine the smallest cardinality of a set B of points with the property that every subspace of dimension k that is contained in Q meets B. It turns out that the smallest examples consist of the non‐singular points of quadrics S ∩ Q for suitable subspaces S of codimension k of PG(d,q). For k = 1, the same result was known before. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 317–338, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10051     

Coloring uniform hypergraphs with few colors

Let m(r, k) denote the minimum number of edges in an r‐uniform hypergraph that is not k‐colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2ⁿ, then m(r, k) ≥ ?(k)k^r(r/ln r)^n/(n+1). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Explicit formula for computing matrix exponential: An analytical approach

This paper is devoted to a practical formula for computing e ^tA, where A is anr×r matrix. Our main result is based on the combinatorial aspect of generalized Fibonacci sequences. Examples and applications are given. Date: June 9, 2003.     

Off‐diagonal and asymptotic results on the Ramsey number r(K2,m,K2,n)

An upper bound on the Ramsey number r(K_2,n‐s,K_2,n) where s ≥ 2 is presented. Considering certain r(K_2,n‐s,K_2,n)‐colorings obtained from strongly regular graphs, we additionally prove that this bound matches the exact value of r(K_2,n‐s,K_2,n) in infinitely many cases if holds. Moreover, the asymptotic behavior of r(K_2,m,K_2,n) is studied for n being sufficiently large depending on m. We conclude with a table of all known Ramsey numbers r(K_2,m,K_2,n) where m,n ≤ 10. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 252–268, 2003     

Snarks with given real flow numbers

We show that for each rational number r such that 4<r?5 there exist infinitely many cyclically 4‐edge‐connected cubic graphs of chromatic index 4 and girth at least 5—that is, snarks—whose flow number equals r. This answers a question posed by Pan and Zhu [Construction of graphs with given circular flow numbers, J Graph Theory 43 [2003], 304–318]. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 189‐201, 2011     

On optimal superimposed codes

A (w,r) cover‐free family is a family of subsets of a finite set such that no intersection of w members of the family is covered by a union of r others. A binary (w,r) superimposed code is the incidence matrix of such a family. Such a family also arises in cryptography as a concept of key distribution patterns. In this paper, we develop a method of constructing superimposed codes and prove that some superimposed codes constructed in this way are optimal. © 2003 Wiley Periodicals, Inc. J Combin Designs 12: 79–71, 2004.     

Non-special divisors on real algebraic curves and embeddings into real projective spaces

We show that there is a large class of non-special divisors of relatively small degree on a given real algebraic curve. If the real algebraic curve has many real components, such a divisor gives rise to an embedding (birational embedding, resp.) of the real algebraic curve into the real projective space ℙ ^r for r≥3 (r=2, resp.). We study these embeddings in quite some detail. Received: October 17, 2001?Published online: February 20, 2003     

Regularized inner products of distorted plane waves and near-forward inverse scattering

Regularized inner products, r(s, e₁, e₂,) of the distorted plane waves fór the plasma wave equation u_u ? Δu + qu = 0 are introduced for potentials with compact support. The regularized inner product may be represented in terms of the far-field pattern. The use of the WKB approximation shows that the behaviour of r as e₂ → ? e₁ is closely related to the Radon transform of q. This observation indicates the possibility of finding the Radon transform of q in terms of r(s, e₁, e₂) and then of recovering q by means of the inverse Radon transform.     

Rational values of the arccosine function

We give a short proof to characterize the cases when arccos(√r), the arccosine of the squareroot of a rational number r ∈ [0, 1], is a rational multiple of π: This happens exactly if r is an integer multiple of 1/4. The proof relies on the well-known recurrence relation for the Chebyshev polynomials of the first kind. Research partially supported by grant BFM2003-06335-C03-03 of the DGI (Spain).     

A dual monotonicity formula for harmonic mappings

The well-known monotonicity formula for harmonic maps says that the scaled energy functional over a ball of radius r is a non-decreasing function of r. The proof uses the fact that the energy functional is critical under any compactly supported variation on the domain of the map. In this article, we will instead use the fact that the energy is critical under variations of the map on the image of the map. By choosing the variational vector field suitably it will be shown that a scaled energy considered as an integral functional over a ball of radius r where r is the distance from a point on the image manifold, is monotonically non-decreasing. The formula takes a stronger form when the image is one dimensional.Received: 29 June 2002, Accepted: 30 September 2002, Published online: 14 February 2003Supported in part by NSF DMS0071862     

Almost all regular graphs are hamiltonian

In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r-regular graphs are hamiltonian for any fixed r ? 3, by an analysis of the distribution of 1-factors in random regular graphs. Moreover, almost all such graphs are r-edge-colorable if they have an even number of vertices. Similarly, almost all r-regular bipartite graphs are hamiltonian and r-edge-colorable for fixed r ? 3. © 1994 John Wiley & Sons, Inc.     

Minors in graphs of large girth

We show that for every odd integer g ≥ 5 there exists a constant c such that every graph of minimum degree r and girth at least g contains a minor of minimum degree at least cr^(g+1)/4. This is best possible up to the value of the constant c for g = 5, 7, and 11. More generally, a well‐known conjecture about the minimal order of graphs of given minimum degree and large girth would imply that our result gives the correct order of magnitude for all odd values of g. The case g = 5 of our result implies Hadwiger's conjecture for C₄‐free graphs of sufficiently large chromatic number. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 213–225, 2003     

A shortness exponent for r-regular r-connected graphs

Let r≧ 3 be an integer. It is shown that there exists ε= ε(r), 0 < ε < 1, and an integer N = N(r) > 0 such that for all n ≧ N (if r is even) or for all even n ≧ N(if r is odd), there is an r-connected regular graph of valency r on exactly n vertices whose longest cycles have fewer than n^ε vertices.