Rainbow number of matchings in planar graphs

The rainbow number$rb(G,H)$ for the graph $H$ in $G$ is defined to be the minimum integer $c$ such that any $c$-edge-coloring of $G$ contains a rainbow $H$. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching $k{K}_2$ in the plane triangulations, where the gap between the lower and upper bounds is $O\left(k^3\right)$. In this paper, we show that the rainbow number of the matching $k{K}_2$ in maximal outerplanar graphs of order $n$ is $n+O\left(k\right)$. Using this technique, we show that the rainbow number of the matching $k{K}_2$ in some subfamilies of plane triangulations of order $n$ is $2n+O\left(k\right)$. The gaps between our lower and upper bounds are only $O\left(k\right)$.     

Perfect matchings in balanced hypergraphs

We generalize Hall's condition for the existence of a perfect matching in a bipartite graph, to balanced hypergraphs.This work was partially supported in part by NSF grants DMI-9424348, DMS-9509581 and ONR grant N00014-89-J-1063. Ajai Kapoor was also supported by a grant from Gruppo Nazionale Delle Riccerche-CNR. Finally, we acknowledge the support of Laboratiore ARTEMIS, Université Joseph Fourier, Grenoble.     

Perfect fractional matchings in random hypergraphs

Given an r-uniform hypergraph H = (V, E) on |V| = n vertices, a real-valued function f:E→R⁺ is called a perfect fractional matching if Σ_vϵe f(e) ≤ 1 for all vϵV and Σ_eϵE f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n→ infinity, at the very moment t₀ when the last isolated vertex disappears, the hypergraph H_t0 has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p(n) = (ln n + w(n))/ , where w(n) is any function tending to infinity with n, then with probability tending to 1 a random r-uniform hypergraph on n vertices with edge probability p has a perfect fractional matching. Similar results hold also for random r-partite hypergraphs. © 1996 John Wiley & Sons, Inc.     

Polynomial-time perfect matchings in dense hypergraphs

Let H be a k-graph on n   vertices, with minimum codegree at least n/k+cn$n/k+cn$ for some fixed c>0$c>0$. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H   or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n/k−cn$n/k-cn$. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.     

Packing perfect matchings in random hypergraphs

We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling. As an illustrative application of this method, we show that for any fixed integer , the binomial ‐uniform random hypergraph contains edge‐disjoint perfect matchings, provided , where is an integer depending only on . Our result for is asymptotically optimal and for is optimal up to the factor. This significantly improves a result of Frieze and Krivelevich.     

Perfect matchings in random s-uniform hypergraphs

Let E = {X₁, X₂…, X_m} where the X_i ? V for 1 ≤ i ≤ m are distinct. The hypergraph G = (V, E) is said to be s-uniform if |X₁| = s for 1 ≤ i ≤ m. A set of edges M = {X_i : i ? I } is a perfect matching if (i) i ≠ j ? I implies X_i ∩ X_i = 0, and (ii) ∪_i?I X_i = V. In this article we consider the question of whether a random s-uniform hypergraph contains a perfect matching. Let s ≥ 3 be fixed and m/n^4/3 → ∞. We show that an s-uniform hypergraph with m edges chosen uniformly from [74] contains a perfect matching with high probability. This improves an earlier result of Schmidt and Shamir who showed that m/n^3/2 → ∞ suffices. © 1995 John Wiley & Sons, Inc.     

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     

Nearly perfect matchings in regular simple hypergraphs

For every fixedk≥3 there exists a constantc _k with the following property. LetH be ak-uniform,D-regular hypergraph onN vertices, in which no two edges contain more than one common vertex. Ifk>3 thenH contains a matching covering all vertices but at mostc _k ND ^−1/(k−1). Ifk=3, thenH contains a matching covering all vertices but at mostc ₃ ND ^−1/2ln^3/2 D. This improves previous estimates and implies, for example, that any Steiner Triple System onN vertices contains a matching covering all vertices but at mostO(N ^1/2ln^3/2 N), improving results by various authors. Research supported in part by a USA-Israel BSF grant. Research supported in part by a USA-Israel BSF Grant.     

Almost perfect matchings in random uniform hypergraphs

We consider the following model H_r(n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = (r − 1)n. Each r-subset of V × (_r−1^U) is chosen to be an edge of H ε H_r(n, p) with probability p = p(n), all choices being independent. It is shown that for every 0 < < 1 if P = (C ln n)/n^r−1 with C = C() sufficiently large, then almost surely every subset V₁ V of size | V₁ | = (1 − )n is matchable, that is, there exists a matching M in H such that every vertex of V₁ is contained in some edge of M.     

Fractional matchings and covers in infinite hypergraphs

A strong version of the duality theorem of linear programming is proved for fractional covers and matchings in countable graphs. It is conjectured to hold for general hypergraphs. In Section 2 we show that in countable hypergraphs there does not necessarily exist a maximal matchable set, contrary to the situation in graphs.