Perfect matchings in random uniform hypergraphs

Let ??_k(n, p) be the random k‐uniform hypergraph on V = [n] with edge probability p. Motivated by a theorem of Erd?s and Rényi 7 regarding when a random graph G(n, p) = ??₂(n, p) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k|n for fixed k ≥ 3, and the expected degree d(n, p) = p(). Then (Erd?s and Rényi 7 proved this for G(n, p).) Assuming d(n, p)/n^1/2 → ∞, Schmidt and Shamir 16 were able to prove that ??_k(n, p) contains a perfect matching with probability 1 ? o(1). Frieze and Janson 8 showed that a weaker condition d(n, p)/n^1/3 → ∞ was enough. In this paper, we further weaken the condition to A condition for a similar problem about a perfect triangle packing of G(n, p) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition p ≥ cn^?2/3+1/15 of Krivelevich 12 , it is shown that if 3|n and p ? n^?2/3+1/18, then © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003     

The phase transition in the cluster‐scaled model of a random graph

For 0 < p < 1 and q > 0 let G_q(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that G_q(n,p)=G is proportional to . The first systematic study of G_q(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of G_q(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

Labeling graphs with two distance constraints

Given a graph G and integers p,q,d₁ and d₂, with p>q, d₂>d₁?1, an L(d₁,d₂;p,q)-labeling of G is a function f:V(G)→{0,1,2,…,n} such that |f(u)−f(v)|?p if d_G(u,v)?d₁ and |f(u)−f(v)|?q if d_G(u,v)?d₂. A k-L(d₁,d₂;p,q)-labeling is an L(d₁,d₂;p,q)-labeling f such that max_v∈V(G)f(v)?k. The L(d₁,d₂;p,q)-labeling number ofG, denoted by , is the smallest number k such that G has a k-L(d₁,d₂;p,q)-labeling. In this paper, we give upper bounds and lower bounds of the L(d₁,d₂;p,q)-labeling number for general graphs and some special graphs. We also discuss the L(d₁,d₂;p,q)-labeling number of G, when G is a path, a power of a path, or Cartesian product of two paths.     

Regular graphs whose subgraphs tend to be acyclic

Motivated by a problem that arises in the study of mirrored storage systems, we describe, for any fixed ε, δ > 0, and any integer d ≥ 2, explicit or randomized constructions of d‐regular graphs on n > n₀(ε, δ) vertices in which a random subgraph obtained by retaining each edge, randomly and independently, with probability , is acyclic with probability at least 1 ? δ. On the other hand we show that for any d‐regular graph G on n > n₁(ε, δ) vertices, a random subgraph of G obtained by retaining each edge, randomly and independently, with probability , does contain a cycle with probability at least 1 ? δ. The proofs combine probabilistic and combinatorial arguments, with number theoretic techniques. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Globally sparse vertex-ramsey graphs

For graphs G and F we write F → (G)¹_r if every r-coloring of the vertices of F results in a monochromatic copy of G. The global density m(F) of F is the maximum ratio of the number of edges to the number of vertices taken over all subgraphs of F. Let We show that The lower bound is achieved by complete graphs, whereas, for all r ≥ 2 and ? > 0, m_cr(S_k, r) > r - ? for sufficiently large k, where S_k is the star with k arms. In particular, we prove that      

Moments of graphs in monotone families

The kth moment of the degree sequence d₁ ≥ d₂ ≥ …d_n of a graph G is . We give asymptotically sharp bounds for μ_k(G) when G is in a monotone family. We use these results for the case k = 2 to improve a result of Pach, Spencer, and Tóth [15]. We answer a question of Erd?s [9] by determining the maximum variance of the degree sequence when G is a triangle‐free n‐vertex graph. © 2005 Wiley Periodicals, Inc.     

On graphs with small Ramsey numbers*

Let R(G) denote the minimum integer N such that for every bicoloring of the edges of K_N, at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each γ,0 < γ < 1, there exists k = k(d,γ) such that for every bipartite graph G = (W,U;E) with the maximum degree of vertices in W at most d and , . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

Random regular graphs of non-constant degree: Concentration of the chromatic number

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model G_n,d for d=o(n^1/5) is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model G(n,p) with . Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for G(n,p) for p=n^−δ where δ>1/2. The main tool used to derive such a result is a careful analysis of the distribution of edges in G_n,d, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.     

Almost Sure Convergence in Extreme Value Theory

Let X₁, …, X_n be independent random variables with common distribution function F. Define and let G(x) be one of the extreme-value distributions. Assume F ∈ D(G), i.e., there exist a_n> 0 and b_n ∈ ? such that . Let l(?∞,x)(·) denote the indicator function of the set (?∞,x) and S(G) =: {x : 0 < G(x) < 1}. Obviously, 1(?∞,x)((M_n?b_n)/a_n) does not converge almost surely for any x ∈ S(G). But we shall prove .     

On the graph of large distances

For a setS of points in the plane, letd ₁>d ₂>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd _k . It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk ². IfS consists of the vertices of a convex polygon and |S|constk ², then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon.     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On uniqueness of Neumann-Tricomi problem in R2

We consider the equation of mixed type (k(y) ? 0 whenever y ? 0) in a region G which is bounded by the curves: A piecewise smooth curve Γ lying in the half-plane y > 0 which intersects the line y = 0 at the points A(-1, 0) and B(0, 0). For y < 0 by a piecewise smooth curve Γ through A which meets the characteristic of (1) issued from B at the point P and the curve Γ which consists of the portion PB of the characteristic through B. We obtain sufficient conditions for the uniqueness of the solution of the problem L[u] = f, d_nu: = k(y)u_xdy – u_ydx|γ0 = = Ψ(s) for a “general” function k(y), when r(x, y) is not necessarily zero and Γ₁ is of a more general form then in the papers of V. P. Egorov [6], [7].     

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d₁≤d₂≤?≤d_n satisfies: for k<n/2, d_k≤min{k+ηn,n/2} implies d_n−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G).     

Posets and planar graphs

A k-decomposition (G₁,…,G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,…,G_k. The classical theorem of Nordhaus and Gaddum bounds χ(G₁) + χ(G₂) and χ(G₁)χ(G₂) over all 2-decompositions of K_n. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K_n) = χ(2;K_n) = χℓ(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K_n), χ(k;K_n), χℓ(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The multiplier conjecture for elementary abelian groups

Applying the method that we presented in [19], in this article we prove: “Let G be an elementary abelian p-group. Let n = dn₁. If d(≠ p) is a prime not dividing n₁, and the order w of d mod p satisfies $ w > \frac{{d^2}}{3} $, then the Second Multiplier Theorem holds without the assumption n₁ > λ, except that only one case is yet undecided: w ≤ d², and $ \frac{{p - 1}}{{2w}} \ge 3 $, and t is a quadratic residue mod p, and t is not congruent to $ x^{\frac{{p - 1}}{{2w}}j} $ (mod p) (1 ≤ j < 2w), where t is an integer meeting the conditions of Second Multiplier Theorem, and x is a primitive root of p.”. © 1994 John Wiley & Sons, Inc.     

Bounded edge-connectivity and edge-persistence of Cartesian product of graphs

The bounded edge-connectivity λ_k(G) of a connected graph G with respect to is the minimum number of edges in G whose deletion from G results in a subgraph with diameter larger than k and the edge-persistence D⁺(G) is defined as λ_d(G)(G), where d(G) is the diameter of G. This paper considers the Cartesian product G₁×G₂, shows λ_k1+k2(G₁×G₂)≥λ_k1(G₁)+λ_k2(G₂) for k₁≥2 and k₂≥2, and determines the exact values of D⁺(G) for G=C_n×P_m, C_n×C_m, Q_n×P_m and Q_n×C_m.     

On the divisor function of sets with even partition functions

Summary For P∈ F₂[z] with P(0)=1 and deg(P)≧ 1, let A =A(P) be the unique subset of N (cf. [9]) such that Σ_n≧0 p(A,n)zⁿ ≡ P(z) mod 2, where p(A,n) is the number of partitions of n with parts in A. To determine the elements of the set A, it is important to consider the sequence σ(A,n) = Σ _{d|n, d∈A} d, namely, the periodicity of the sequences (σ(A,2^kn) mod 2^k+1)_n≧1 for all k ≧ 0 which was proved in [3]. In this paper, the values of such sequences will be given in terms of orbits. Moreover, a formula to σ(A,2^kn) mod 2^k+1 will be established, from which it will be shown that the weight σ(A₁,2^kz_i) mod 2^k+1 on the orbit <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>z_i$ is moved on some other orbit z_j when A₁ is replaced by A₂ with A₁= A(P₁) and A₂= A(P₂) P₁ and P₂ being irreducible in F₂[z] of the same odd order.     

On the existence of cycle frames and almost resolvable cycle systems

Suppose H is a complete m-partite graph K_m(n₁,n₂,…,n_m) with vertex set V and m independent sets G₁,G₂,…,G_m of n₁,n₂,…,n_m vertices respectively. Let G={G₁,G₂,…,G_m}. If the edges of λH can be partitioned into a set C of k-cycles, then (V,G,C) is called a k-cycle group divisible design with index λ, denoted by (k,λ)-CGDD. A (k,λ)-cycle frame is a (k,λ)-CGDD (V,G,C) in which C can be partitioned into holey 2-factors, each holey 2-factor being a partition of V?G_i for some G_i∈G. Stinson et al. have resolved the existence of (3,λ)-cycle frames of type g^u. In this paper, we show that there exists a (k,λ)-cycle frame of type g^u for k∈{4,5,6} if and only if , , u≥3 when k∈{4,6}, u≥4 when k=5, and (k,λ,g,u)≠(6,1,6,3). A k-cycle system of order n whose cycle set can be partitioned into (n−1)/2 almost parallel classes and a half-parallel class is called an almost resolvable k-cycle system, denoted by k-ARCS(n). Lindner et al. have considered the general existence problem of k-ARCS(n) from the commutative quasigroup for . In this paper, we give a recursive construction by using cycle frames which can also be applied to construct k-ARCS(n)s when . We also update the known results and prove that for k∈{3,4,5,6,7,8,9,10,14} there exists a k-ARCS(2kt+1) for each positive integer t with three known exceptions and four additional possible exceptions.