Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

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     

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     

Regular induced subgraphs of a random Graph

An old problem of Erd?s, Fajtlowicz, and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on vertices, i.e., in a binomial random graph . We prove that with high probability a largest induced regular subgraph of has about vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235–250, 2011     

Hamilton decompositions of complete multipartite graphs with any 2-factor leave

For m ≥ 1 and p ≥ 2, given a set of integers s₁,…,s_q with for and , necessary and sufficient conditions are found for the existence of a hamilton decomposition of the complete p-partite graph , where U is a 2-factor of consisting of q cycles, the jth cycle having length s_j. This result is then used to completely solve the problem when p = 3, removing the condition that . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 208–214, 2003     

On the Eigenvalues of Half‐Linear Boundary Value Problems

We consider the half‐linear boundary value problem where and the weight function q is assumed to change sign. We prove the existence of two sequences , of eigenvalues and derive asymptotic estimates for as .     

On asymmetric coverings and covering numbers

An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022     

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.     

Small degree out‐branchings

Using a suitable orientation, we give a short proof of a strengthening of a result of Czumaj and Strothmann 4 : Every 2‐edge‐connected graph G contains a spanning tree T with the property that for every vertex v. As an analogue of this result in the directed case, we prove that every 2‐arc‐strong digraph D has an out‐branching B such that . A corollary of this is that every k‐arc‐strong digraph D has an out‐branching B such that , where . We conjecture that in this case would be the right (and best possible) answer. If true, this would again imply a strengthening of a result from 4 concerning spanning trees with small degrees in k‐connected graphs when k ≥ 2. We prove that for acyclic digraphs the existence of an out‐branching satisfying prescribed bounds on the out‐degrees of each vertex can be checked in polynomial time. A corollary of this is that the existence of arc‐disjoint branchings , , where the first is an out‐branching rooted at s and the second an in‐branching rooted at t, can be checked in polynomial time for the class of acyclic digraphs © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 297–307, 2003     

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.     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

The generalized Randić index of trees

The generalized Randi?; index of a tree T is the sum over the edges of T of where is the degree of the vertex x in T. For all , we find the minimal constant such that for all trees on at least 3 vertices, , where is the number of vertices of T. For example, when . This bound is sharp up to the additive constant—for infinitely many n we give examples of trees T on n vertices with . More generally, fix and define , where is the number of leaves of T. We determine the best constant such that for all trees on at least 3 vertices, . Using these results one can determine (up to terms) the maximal Randi?; index of a tree with a specified number of vertices and leaves. Our methods also yield bounds when the maximum degree of the tree is restricted. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 270–286, 2007     

Random coloring method in the combinatorial problem of Erdős and Lovász

The work deals with a combinatorial problem of P. Erd?s and L. Lovász concerning simple hypergraphs. Let denote the minimum number of edges in an n‐uniform simple hypergraph with chromatic number at least . The main result of the work is a new asymptotic lower bound for . We prove that for large n and r satisfying the following inequality holds where . This bound improves previously known bounds for . The proof is based on a method of random coloring. We have also obtained results concerning colorings of h‐simple hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

A Relation between Mean Curvature Flow Solitons and Minimal Submanifolds

We derive a one to one correspondence between conformal solitons of the mean curvature flow in an ambient space N and minimal submanifolds in a different ambient space where equals ℝ × N equipped with a warped product metric and show that a submanifold inN converges to a conformal soliton under the mean curvature flow in N if and only if its associatedsubmanifold in converges to a minimal submanifold under a rescaled mean curvature flow in . We then define a notion of stability for conformal solitons and obtain L^p estimates as well as pointwise estimates for the curvature of stable solitons.     

A generalization of the Oberwolfach problem

Let n > 1 be an integer and let a₂,a₃,…,a_n be nonnegative integers such that . Then can be factored into ‐factors, ‐factors,…, ‐factors, plus a 1‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 151–161, 2002     

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 .     

Uniqueness of Integrable Solutions ∇ζ = Gζ, ζ∣Γ = 0 for Integrable Tensor-Coefficients G and Applications to Elasticity

Let be bounded Lipschitz and relatively open. We show that the solution to the linear first order system 1 : (1) vanishes if and , (e.g. ). We prove to be a norm if with , for some p, q > 1 with 1/p + 1/q = 1 and . We give a new proof for the so called ‘in-finitesimal rigid displacement lemma’ in curvilinear coordinates: Let , satisfy for some with . Then there are and a constant skew-symmetric matrix , such that . (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Compactness Conditions for the Green Operator in Lp(ℝ) Corresponding to a General Sturm–Liouville Operator

We consider the equation ℝ, where , for ℝ, (ℝ), (ℝ), (ℝ), (ℝ) := C(ℝ)). We give necessary and sufficient conditions under which, regardless of , the following statements hold simultaneously: I) For any (ℝ) Equation (0.1) has a unique solution (ℝ) where $\int ^{\infty}_{-\infty}$ ℝ. II) The operator (ℝ) → (ℝ) is compact. Here is the Green function corresponding to (0.1). This result is applied to study some properties of the spectrum of the Sturm–Liouville operator.     

Infinite games in the Cantor space and subsystems of second order arithmetic

In this paper we study the determinacy strength of infinite games in the Cantor space and compare them with their counterparts in the Baire space. We show the following theorems: 1. RCA₀ ? ‐Det* ? ‐Det* ? WKL₀. 2. RCA₀ ? ( )2‐Det* ? ACA₀. 3. RCA₀ ? ‐Det* ? ‐Det* ? ‐Det ? ‐Det ? ATR₀. 4. For 1 < k < ω, RCA₀ ? ( )_k ‐Det* ? ( )_{k –1}‐Det. 5. RCA₀ ? ‐Det* ? ‐Det. Here, Det* (respectively Det) stands for the determinacy of infinite games in the Cantor space (respectively the Baire space), and ( )_k is the collection of formulas built from formulas by applying the difference operator k – 1 times. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.