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     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

Covering arrays with mixed alphabet sizes

Covering arrays with mixed alphabet sizes, or simply mixed covering arrays, are natural generalizations of covering arrays that are motivated by applications in software and network testing. A (mixed) covering array A of type is a k × N array with the cells of row i filled with elements from ? and having the property that for every two rows i and j and every ordered pair of elements (e,f) ∈ ? × ?, there exists at least one column c, 1 ≤ c ≤ N, such that A_i,c = e and A_j,c = f. The (mixed) covering array number, denoted by , is the minimum N for which a covering array of type with N columns exists. In this paper, several constructions for mixed covering arrays are presented, and the mixed covering array numbers are determined for nearly all cases with k = 4 and for a number of cases with k = 5. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 413–432, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10059     

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)     

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

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     

Edge-colored saturated graphs

A graph G is (k₁, k₂, …, k_t)-saturated if there exists a coloring C of the edges of G in t colors 1, 2, …, t in such a way that there is no monochromatic complete k_i-subgraph K of color i, 1 ? i ? t, but the addition of any new edge of color i, joining two nonadjacent vertices in G, with C, creates a monochromatic K of color i, 1 ? i ? t. We determine the maximum and minimum number of edges in such graphs and characterize the unique extremal graphs.     

More results on perfect (3,3,6k + 4; 6k − 2)‐threshold schemes

A (2,3)‐packing on X is a pair (X, ), where is a set of 3‐subsets (called blocks) of X, such that any pair of distinct points from X occurs together in at most one block. Its leave is a graph (X,E) such that E consists of all the pairs which do not appear in any block of . In this article, we shall construct a set of 6k ? 2 disjoint (2,3)‐packings of order 6k + 4 with K_1,3 ∪ 3kK₂ or G₁ ∪ (3k ? 1)K₂ as their common leave for any integer k ≥ 1 with a few possible exceptions (G₁ is a special graph of order 6). Such a system can be used to construct perfect threshold schemes as noted by Schellenberg and Stinson ( 22 ). © 2006 Wiley Periodicals, Inc. J Combin Designs     

On an online random k‐SAT model

Given n Boolean variables x₁,…,x_n, a k‐clause is a disjunction of k literals, where a literal is a variable or its negation. Suppose random k‐clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated k‐clauses as possible with the condition that it must be possible to satisfy every clause that is accepted. When cn random k‐clauses on n variables are given, a natural online algorithm known as Online‐Lazy accepts an expected (1 ? )cn + a_kn clauses for some constant a_k. If these clauses are given offline, it is possible to do much better, (1 ? )cn + Ω( )n can be accepted whp . The question of closing the gap between a_k and Ω( ) for the online version remained open. This article shows that for any k ≥ 1, any online algorithm will accept less than (1 ? )cn + (ln 2)n k‐clauses whp , closing the gap between the constant and Ω( ). Furthermore we show that this bound is asymptotically tight as k → ∞. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Partitions of finite vector spaces into subspaces

Let V_n(q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V_n(q) is a partition of V_n(q) if every nonzero element of V_n(q) is contained in exactly one element of . Suppose there exists a partition of V_n(q) into x_i subspaces of dimension n_i, 1 ≤ i ≤ k. Then x₁, …, x_k satisfy the Diophantine equation . However, not every solution of the Diophantine equation corresponds to a partition of V_n(q). In this article, we show that there exists a partition of V_n(2) into x subspaces of dimension 3 and y subspaces of dimension 2 if and only if 7x + 3y = 2ⁿ ? 1 and y ≠ 1. In doing so, we introduce techniques useful in constructing further partitions. We also show that partitions of V_n(q) induce uniformly resolvable designs on qⁿ points. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 329–341, 2008     

Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphs

In any r‐uniform hypergraph for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ?, denoted by C_?^{(r, t)}, as a sequence of distinct vertices v₁, v₂, … , v_?, such that for each set (v_i, v_{i + 1}, … , v_{i + t ? 1}) of t consecutive vertices on the cycle, there is an edge E_i of that contains these t vertices and the edges E_i are all distinct for i, 1 ≤ i ≤ ?, where ? + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of K_n^(r), the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008     

Nodes of large degree in random trees and forests

We study the asymptotic behavior of the number N_k,n of nodes of given degree k in unlabeled random trees, when the tree size n and the node degree k both tend to infinity. It is shown that N_k,n is asymptotically normal if and asymptotically Poisson distributed if . If , then the distribution degenerates. The same holds for rooted, unlabeled trees and forests. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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     

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 irregularity strength of trees

For any graph G, let n_i be the number of vertices of degree i, and . This is a general lower bound on the irregularity strength of graph G. All known facts suggest that for connected graphs, this is the actual irregularity strength up to an additive constant. In fact, this was conjectured to be the truth for regular graphs and for trees. Here we find an infinite sequence of trees with λ(T) = n₁ but strength converging to . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 241–254, 2004     

An asymptotic version of a conjecture by Enomoto and Ota

In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let G be a graph of order n, and let n₁, n₂, …, n_k be positive integers with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} {{n}}_{{{i}}} = {{n}}\end{eqnarray*}. If σ₂(G)≥n+ k?1, then for any k distinct vertices x₁, x₂, …, x_k in G, there exist vertex disjoint paths P₁, P₂, …, P_k such that |P_i|=n_i and x_i is an endpoint of P_i for every i, 1≤i≤k. We prove an asymptotic version of this conjecture in the following sense. For every k positive real numbers γ₁, …, γ_k with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} \gamma_{{{i}}} = {{1}}\end{eqnarray*}, and for every ε>0, there exists n₀ such that for every graph G of order n≥n₀ with σ₂(G)≥n+ k?1, and for every choice of k vertices x₁, …, x_k∈V(G), there exist vertex disjoint paths P₁, …, P_k in G such that \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} |{{P}}_{{{i}}}| = {{n}}\end{eqnarray*}, the vertex x_i is an endpoint of the path P_i, and (γ_i?ε)n<|P_i|<(γ_i + ε)n for every i, 1≤i≤k. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010     

Energy Estimates and Cavity Interaction for a Critical‐Exponent Cavitation Model

We consider the minimization of in a perforated domain of among maps that are incompressible (det ) and invertible, and satisfy a Dirichlet boundary condition u = g on ?Ω. If the volume enclosed by g (?Ω) is greater than |Ω|, any such deformation u is forced to map the small holes B_ε( a _i) onto macroscopically visible cavities (which do not disappear as ε → 0). We restrict our attention to the critical exponent p = n, where the energy required for cavitation is of the order of and the model is suited, therefore, for an asymptotic analysis (v₁,…, v_M denote the volumes of the cavities). In the spirit of the analysis of vortices in Ginzburg‐Landau theory, we obtain estimates for the “renormalized” energy showing its dependence on the size and the shape of the cavities, on the initial distance between the cavitation points a ₁,…, a _M, and on the distance from these points to the outer boundary ?Ω. Based on those estimates we conclude, for the case of two cavities, that either the cavities prefer to be spherical in shape and well separated, or to be very close to each other and appear as a single equivalent round cavity. This is in agreement with existing numerical simulations and is reminiscent of the interaction between cavities in the mechanism of ductile fracture by void growth and coalescence. © 2012 Wiley Periodicals, Inc.     

Tauberian theorem for m‐spherical transforms on the Heisenberg group

In this paper we prove a Tauberian type theorem for the space L ( H _n ). This theorem gives sufficient conditions for a L ( H _n ) submodule J ? L ( H _n ) to make up all of L ( H _n ). As a consequence of this theorem, we are able to improve previous results on the Pompeiu problem with moments on the Heisenberg group for the space L^∞( H _n ). In connection with the Pompeiu problem, given the vanishing of integrals ∫ z ^m L _g f ( z , 0) dσ ( z ) = 0 for all g ∈ H _n and i = 1, 2 for appropriate radii r₁ and r₂, we now have the (improved) conclusion f ≡ 0, where = · · · and form the standard basis for T^(0,1)( H _n ). (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A generalization of a result of Tran Van Trung on t-designs

We prove that if there exists a t − (v, k, λ) design satisfying the inequality for some positive integer j (where m = min{j, v − k} and n = min {i, t}), then there exists a t − (v + j, k, λ ()) design. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 107–112, 1999     

A sharp edge bound on the interval number of a graph

The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Namely, it is shown that i(G) ≤ + 1. It is also observed that the edge bound induces i(G) ≤ , where γ(G) is the genus of G. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 153–159, 1999