The isoperimetric constant of the random graph process

The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of , taken over all nonempty subsets S ⊂ V (G) of size at most n/2, where ∂S denotes the set of edges with precisely one end in S. A random graph process on n vertices, , is a sequence of graphs, where is the edgeless graph on n vertices, and is the result of adding an edge to , uniformly distributed over all the missing edges. The authors show that in almost every graph process equals the minimal degree of as long as the minimal degree is o(log n). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to , its final value. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The circular chromatic number of the Mycielskian of G

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χ_c(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χ_c(G) = and χ(G) = , consequently, there exist graphs G such that χ_c(G) is as close to χ(G) − 1 as you want, but χ_c(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999     

A list analogue of equitable coloring

Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most vertices. A graph is equitably k-choosable if such a coloring exists whenever the lists all have size k. We prove that G is equitably k-choosable when unless G contains or k is odd and . For forests, the threshold improves to . If G is a 2-degenerate graph (given k ≥ 5) or a connected interval graph (other than ), then G is equitably k-choosable when . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 166–177, 2003     

Coloring edges of embedded graphs

In this paper, we prove that any graph G with maximum degree , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000     

On a conjecture of Thomassen and Toft

This article is motivated by a conjecture of Thomassen and Toft on the number s₂(G) of separating vertex sets of cardinality 2 and the number υ₂(G) of vertices of degree 2 in a graph G belonging to the class 𝒢 of all 2-connected graphs without nonseparating induced cycles. Let ‖G‖ denote the number of edges of the graph G. Thomassen and Toft conjectured in [C. Thomassen & B. Toft, J. Combin. Theory B 31 (1981), 199–224] the existence of a positive constant c satisfying s₂(G) + υ₂(G) > c · ‖G‖ for all G ∈ 𝒢. We shall see that this is not true in general. Restricting ourselves to planar graphs, we obtain s₂(G) + υ₂(G) > · ‖G‖ for all planar G ∈ 𝒢, where is best-possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 118–122, 1999     

Quasilinear degenerate parabolic equations of Kirchhoff type

We investigate the evolution problem where H is a Hilbert space, A is a self‐adjoint linear non‐negative operator on H with domain D(A), and is a continuous function. We prove that if , and , then there exists at least one global solution, which is unique if either m never vanishes, or m is locally Lipschitz continuous. Moreover, we prove that if for all , then this problem is well posed in H. On the contrary, if for some it happens that for all , then this problem has no solution if with β small enough. We apply these results to degenerate parabolic PDEs with non‐local non‐linearities. Copyright © 1999 John Wiley & Sons, Ltd.     

Spanning trees with many leaves

We show that if G is a simple connected graph with and , then G has a spanning tree with > t leaves, and this is best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 189–197, 2001     

Strengths and Weaknesses of LH Arithmetic

In this paper we provide a new arithmetic characterization of the levels of the og‐time hierarchy (LH). We define arithmetic classes and that correspond to ‐LOGTIME and ‐LOGTIME, respectively. We break and into natural hierarchies of subclasses and . We then define bounded arithmetic deduction systems ′ whose ‐definable functions are precisely B( ‐LOGTIME). We show these theories are quite strong in that (1) LIOpen proves for any fixed m that , (2) TAC, a theory that is slightly stronger than ′ whose (LH)‐definable functions are LH, proves LH is not equal to ‐TIME(s) for any m> 0, where 2^s ∈L, s(n) ∈ ω(log n), and (3) TAC proves LH ≠ for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours.     

On the Range of Two Convolution Operators

Let _(ω)(ℝ) denote the non–quasianalytic class of Beurling type on ℝ. For μ, ν ∈ ′_(ω)(ℝ) we give necessary conditions for the inclusion T_ν( _(ω)(ℝ)) ⊂ T_μ( _(ω)(ℝ)), thus extending previous work of Malgrange and Ehrenpreis .     

Total relative displacement of vertex permutations of K

Let α denote a permutation of the n vertices of a connected graph G. Define δ_α(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δ_α(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δ_α(G) = 0. Let π(G) denote the smallest positive value of δ_α(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δ_α(G) has been called a near‐automorphism of G [ 2 ]. We determine π(K) and describe permutations α of K for which π(K) = δ_α(K). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to n_i,1≤i≤t. We prove that for positive integers, n₁≤n₂≤…≤n_t, where t≥2 and n_t≥2, where k₀ is the smallest index for which n = n+1. As a special case, we correct the value of π(K_m,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [ 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002     

Upper total domination in claw‐free graphs

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ_t(G). We establish bounds on Γ_t(G) for claw‐free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that if if , and if δ ≥ 5. The extremal graphs are characterized. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 148–158, 2003     

Comparing Packing Measures to Hausdorff Measures on the Line

For each 0 < s < 1, define where , denote respectively the s‐dimensional packing measure and Hausdorff measure, and the infimum is taken over all the sets E ⊂ R with . In this paper we give a nontrivial estimation of c(s), namely, for each 0 < s < 1, where . As an application, we obtain a lower density theorem for Hausdorff measures.     

The color space of a graph

If k is a prime power, and G is a graph with n vertices, then a k‐coloring of G may be considered as a vector in $\mathbb{GF}$(k)ⁿ. We prove that the subspace of $\mathbb{GF}$(3)ⁿ spanned by all 3‐colorings of a planar triangle‐free graph with n vertices has dimension n. In particular, any such graph has at least n − 1 nonequivalent 3‐colorings, and the addition of any edge or any vertex of degree 3 results in a 3‐colorable graph. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 234–245, 2000     

On Local Invertible Operators in L2 (ℝ1, H)

We study operators of the form Lu = — G(t) u(t) in L²([t₀ — δ, t₀ + δ], H) with = L² ([t₀— δ, t₀ + δ], H ) in the neighbourhood [t₀— δ, t₀ + δ] of a point t₀ ∈ ℝ¹. Such problems arise in questions on local solvability of partial differential equations (see [6] and [7]). For these operators,one of the major questions is if they are invertible in a neighbourhood of a point t ∈ ℝ¹. To solve this problem we establish needed commutator estimates. Using the commutator estimates and factorization theorems for nonanalytic operator-functions we give additional conditions for the nonanalytic operator -function G(t) and show that the operator L (or ) with some boundary conditions is local invertible.     

On the Additive Group Structure of the Nonstandard Models of the Theory of Integers

Let $\hat \mathbb{Z}$ denote the inverse limit of all finite cyclic groups. Let F, G and H be abelian groups with H ≤ G. Let FβH denote the abelian group (F × H, +^β), where +^βis defined by (a, x) +^β (b, y) = (a + b, x + y + β(a) + β(b) — β(a + b)) for a certain β : F → G linear mod H meaning that β(0) = 0 and β(a) + β(b) — β(a + b) ∈ H for all a, b in F. In this paper we show that the following hold: (1) The additive group of any nonstandard model ℤ* of the ring ℤ is isomorphic to (ℤ*₊/H)βH for a certain β : ℤ*₊/H → $\hat \mathbb{Z}$ linear mod H. (2) $\hat \mathbb{Z}$ is isomorphic to (ℤ₊/H )βH for some β : $\hat \mathbb{Z}$/H →ℚ linear mod H, though $\hat \mathbb{Z}$ is not the additive group of any model of Th(ℤ, +, ×) and the exact sequence H → $\hat \mathbb{Z}$ → $\hat \mathbb{Z}$/H is not splitting.     

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs , we describe the critical group structure completely. For Cartesian products of complete graphs , we generalize results of H. Bai on the k-dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p-primary structure for all primes p that divide none of . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 231–250, 2003     

Circular choosability via combinatorial Nullstellensatz

A p‐list assignment L of a graph G assigns to each vertex v of G a set of permissible colors. We say G is L‐(P, q)‐colorable if G has a (P, q)‐coloring h such that h(v) ? L(v) for each vertex v. The circular list chromatic number of a graph G is the infimum of those real numbers t for which the following holds: For any P, q, for any P‐list assignment L with , G is L‐(P, q)‐colorable. We prove that if G has an orientation D which has no odd directed cycles, and L is a P‐list assignment of G such that for each vertex v, , then G is L‐(P, q)‐colorable. This implies that if G is a bipartite graph, then , where is the maximum average degree of a subgraph of G. We further prove that if G is a connected bipartite graph which is not a tree, then . © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 190–204, 2008     

On the Points on the Unit Circle with Finite b–Adic Expansions

Let be an arbitrary integer base and let be the number of different prime factors of with , . Further let be the set of points on the unit circle with finite –adic expansions of their coordinates and let be the set of angles of the points . Then is an additive group which is the direct sum of infinite cyclic groups and of the finite cyclic group . If in case of the points of are arranged according to the number of digits of their coordinates, then the arising sequence is uniformly distributed on the unit circle. On the other hand, in case of the only points in are the exceptional points (1, 0), (0, 1), (–1, 0), (0, –1). The proofs are based on a canonical form for all integer solutions of .     

The phase transition in the evolution of random digraphs

Let $ \mathop {\rm D}\limits^ \to $(n, M) denote a digraph chosen at random from the family of all digraphs on n vertices with M arcs. We shall prove that if M/n ≤ c < 1 and ω(n) → ∞, then with probability tending to 1 as n → ∞ all components of $ \mathop {\rm D}\limits^ \to $(n, M) are smaller than ω(n), whereas when M/n ≥ c > 1 the largest component of $ \mathop {\rm D}\limits^ \to $(n, M) is of the order n with probability 1 - o(1).     

The ground state eigenvalue of Hill's equation with white noise potential

The distribution of the ground state eigenvalue λ₀(Q) of Hill's operator Q = −d²/dx² + q(x) on the circle of perimeter 1 is expressed in two different ways in case the potential q is standard white noise. Let WN be the associated white noise measure, and let CBM be the measure for circular Brownian motion p(x), 0 ≤ x < 1, formed from the standard Brownian motion b(x), 0 ≤ x ≤ 1, starting at b(0) = a, by conditioning so that b(1) = a, and distributing this common level over the line according to the measure da. The connection is based upon the Ricatti correspondence q(x) = λ + p′ (x) + p²(x). The two versions of the distribution are (1) in which $\overline{p}$ is the mean value ∫ pdx, and (2) the left‐hand side of (2) being the density for (1) and CBM₀ the conditional circular Brownian measure on $\overline{p}$ = 0. (1) and (2) are related by the divergence theorem in function space as suggested by the recognition of the Jacobian factor the outward‐pointing normal component of the vector field v(x) = ∂Δ(λ)/∂q(x), 0 ≤ x < 1, Δ being the Hill's discriminant for Q. The Ricatti correspondence prompts the idea that (1) and (2) are instances of the Cameron‐Martin formula, but it is not so: The latter has to do with the initial value problem for Ricatti, but it is the periodic problem that figures here, so the proof must be done by hand, by finite‐dimensional approximation. The adaptation of 1 and 2 to potentials of Ornstein‐Uhlenbeck type is reported without details. © 1999 John Wiley & Sons, Inc.