Rainbow matchings in Dirac bipartite graphs

We show the existence of rainbow perfect matchings in μn‐bounded edge colorings of Dirac bipartite graphs, for a sufficiently small μ > 0. As an application of our results, we obtain several results on the existence of rainbow k‐factors in Dirac graphs and rainbow spanning subgraphs of bounded maximum degree on graphs with large minimum degree.     

Dense graphs with small clique number

We consider the structure of K_r‐free graphs with large minimum degree, and show that such graphs with minimum degree δ>(2r ? 5)n/(2r ? 3) are homomorphic to the join K_{r ? 3}∨H, where H is a triangle‐free graph. In particular this allows us to generalize results from triangle‐free graphs and show that K_r‐free graphs with such a minimum degree have chromatic number at most r +1. We also consider the minimum‐degree thresholds for related properties. Copyright © 2010 John Wiley & Sons, Ltd. 66:319‐331, 2011     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

Asymptotic enumeration of sparse 2‐connected graphs

We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

A characterization of weakly four‐connected graphs

A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G ? x is 2‐edge‐connected for all x ∈ V. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006     

Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a random k‐coloring of a random graph G_n,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Matchings in hypergraphs of large minimum degree

It is well known that every bipartite graph with vertex classes of size n whose minimum degree is at least n/2 contains a perfect matching. We prove an analog of this result for hypergraphs. We also prove several related results that guarantee the existence of almost perfect matchings in r‐uniform hypergraphs of large minimum degree. Our bounds on the minimum degree are essentially best possible. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 269–280, 2006     

Bounded transversals in multipartite graphs

Transversals in r‐partite graphs with various properties are known to have many applications in graph theory and theoretical computer science. We investigate f‐bounded transversal s (or f‐BT), that is, transversals whose connected components have order at most f. In some sense we search for the sparsest f‐BT‐free graphs. We obtain estimates on the smallest maximum degree that 3‐partite and 4‐partite graphs without 2‐BT can have and provide a greatly simplified proof of the best known general lower bound on the smallest maximum degree in f‐BT‐free graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

Non‐isolated quasi‐degrees

We show that non‐isolated from below 2‐c.e. Q ‐degrees are dense in the structure of c.e. Q ‐degrees. We construct a 2‐c.e. Q ‐degree, which can't be isolated from below not only by c.e. Q ‐degrees, but by any Q ‐degree. We also prove that below any c.e. Q ‐degree there is a 2‐c.e. Q ‐degree, which is non‐isolated from below and from above (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Vertices of given degree in series‐parallel graphs

We show that the numbers of vertices of a given degree k ≥ 1 in several kinds of series‐parallel labeled graphs of size n satisfy a central limit theorem with mean and variance proportional to n, and quadratic exponential tail estimates. We further prove a corresponding theorem for the number of nodes of degree two in labeled planar graphs. The proof method is based on generating functions and singularity analysis. In particular, we need systems of equations for multivariate generating functions and transfer results for singular representations of analytic functions. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Improvements for some condition number estimates for preconditioned system in p‐FEM

In this paper, we consider domain decomposition preconditioners for a system of linear algebraic equations arising from the p‐version of the FEM. We analyse several multi‐level preconditioners for the Dirichlet problems in the sub‐domains in two and three dimensions. It is proved that the condition number of the preconditioned system is bounded by a constant independent of the polynomial degree. Relations between the p‐version of the FEM and the h‐version are helpful in the interpretations of the results. Copyright © 2006 John Wiley & Sons, Ltd.     

On convolutions of Siegel modular forms

In this article we study a Rankin‐Selberg convolution of n complex variables for pairs of degree n Siegel cusp forms. We establish its analytic continuation to ?ⁿ, determine its functional equations and find its singular curves. Also, we introduce and get similar results for a convolution of degree n Jacobi cusp forms. Furthermore, we show how the relation of a Siegel cusp form and its Fourier‐Jacobi coefficients is reflected in a particular relation connecting the two convolutions studied in this paper. As a consequence, the Dirichlet series introduced by Kalinin [7] and Yamazaki [19] are obtained as particular cases. As another application we generalize to any degree the estimate on the size of Fourier coefficients given in [14]. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the bounded quasi‐degrees of c.e. sets

We study the degree structure of bQ‐reducibility and we prove that for any noncomputable c.e. incomplete bQ‐degree a, there exists a nonspeedable bQ‐degree incomparable with it. The structure $\mathcal {D}_{\mbox{bs}}$ of the $\mbox{bs}$‐degrees is not elementary equivalent neither to the structure of the $\mbox{be}$‐degrees nor to the structure of the $\mbox{e}$‐degrees. If c.e. degrees a and b form a minimal pair in the c.e. bQ‐degrees, then a and b form a minimal pair in the bQ‐degrees. Also, for every simple set S there is a noncomputable nonspeedable set A which is bQ‐incomparable with S and bQ‐degrees of S and A does not form a minimal pair.     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

Arithmetic of divisibility in finite models

We prove that the finite‐model version of arithmetic with the divisibility relation is undecidable (more precisely, it has Π⁰₁‐complete set of theorems). Additionally we prove FM‐representability theorem for this class of finite models. This means that a relation R on natural numbers can be described correctly on each input on almost all finite divisibility models if and only if R is of degree ≤ 0 ′. We obtain these results by interpreting addition and multiplication on initial segments of finite models with divisibility only. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments

Given a k‐arc‐strong tournament T, we estimate the minimum number of arcs possible in a k‐arc‐strong spanning subdigraph of T. We give a construction which shows that for each k ≥ 2, there are tournaments T on n vertices such that every k‐arc‐strong spanning subdigraph of T contains at least arcs. In fact, the tournaments in our construction have the property that every spanning subdigraph with minimum in‐ and out‐degree at least k has arcs. This is best possible since it can be shown that every k‐arc‐strong tournament contains a spanning subdigraph with minimum in‐ and out‐degree at least k and no more than arcs. As our main result we prove that every k‐arc‐strong tournament contains a spanning k‐arc‐strong subdigraph with no more than arcs. We conjecture that for every k‐arc‐strong tournament T, the minimum number of arcs in a k‐arc‐strong spanning subdigraph of T is equal to the minimum number of arcs in a spanning subdigraph of T with the property that every vertex has in‐ and out‐degree at least k. We also discuss the implications of our results on related problems and conjectures. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 265–284, 2004     

2‐ and 3‐factors of graphs on surfaces

It has been conjectured that any 5‐connected graph embedded in a surface Σ with sufficiently large face‐width is hamiltonian. This conjecture was verified by Yu for the triangulation case, but it is still open in general. The conjecture is not true for 4‐connected graphs. In this article, we shall study the existence of 2‐ and 3‐factors in a graph embedded in a surface Σ. A hamiltonian cycle is a special case of a 2‐factor. Thus, it is quite natural to consider the existence of these factors. We give an evidence to the conjecture in a sense of the existence of a 2‐factor. In fact, we only need the 4‐connectivity with minimum degree at least 5. In addition, our face‐width condition is not huge. Specifically, we prove the following two results. Let G be a graph embedded in a surface Σ of Euler genus g.

• (1) If G is 4‐connected and minimum degree of G is at least 5, and furthermore, face‐width of G is at least 4g?12, then G has a 2‐factor.
• (2) If G is 5‐connected and face‐width of G is at least max{44g?117, 5}, then G has a 3‐factor.

The connectivity condition for both results are best possible. In addition, the face‐width conditions are necessary too. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 67:306‐315, 2011     

Hitting time results for Maker‐Breaker games

We study Maker‐Breaker games played on the edge set of a random graph. Specifically, we analyze the moment a typical random graph process first becomes a Maker's win in a game in which Maker's goal is to build a graph which admits some monotone increasing property \begin{align*}\mathcal{P}\end{align*}. We focus on three natural target properties for Maker's graph, namely being k ‐vertex‐connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the k ‐vertex connectivity game exactly at the time the random graph process first reaches minimum degree 2k; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree 2; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree 4. The latter two statements settle conjectures of Stojakovi? and Szabó. We also prove generalizations of the latter two results; these generalizations partially strengthen some known results in the theory of random graphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009