Embedding Factorizations for 3‐Uniform Hypergraphs

In this article, two results are obtained on a hypergraph embedding problem. The proof technique is itself of interest, being the first time amalgamations have been used to address the embedding of hypergraphs. The first result finds necessary and sufficient conditions for the embedding a hyperedge‐colored copy of the complete 3‐uniform hypergraph of order m, , into an r‐factorization of , providing that . The second result finds necessary and sufficient conditions for an embedding when not only are the colors of the hyperedges of given, but also the colors of all the “pieces” of hyperedges on these m vertices are prescribed (the “pieces” of hyperedges are eventually extended to hyperedges of size 3 in by adding new vertices to the hyperedges of size 1 and 2 during the embedding process). Both these results make progress toward settling an old question of Cameron on completing partial 1‐factorizations of hypergraphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 216–224, 2013     

Tiling 3‐Uniform Hypergraphs With

Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3‐uniform hypergraph G of order n with minimum pair‐degree contains vertex‐disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636).     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.     

Degree Conditions for Matchability in 3‐Partite Hypergraphs

We study conjectures relating degree conditions in 3‐partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko [14] (as generalized by the first two authors [2]), that every family of $2n-1$ matchings of size n in a bipartite graph has a partial rainbow matching of size n. We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless [11], that every $n\times n$ Latin square has a generalized diagonal (set of n entries, each in a different row and column) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row‐Latin.     

Large Sets of Wrapped K–K Hamilton Cycle Decompositions of Complete Bipartite 3‐Uniform Hypergraphs

Using the Katona–Kierstead (K–K) definition of a Hamilton cycle in a uniform hypergraph, we investigate the existence of wrapped K–K Hamilton cycle decompositions of the complete bipartite 3‐uniform hypergraph and their large sets, settling their existence whenever n is prime.     

On 2‐Colorings of Hypergraphs

In this article, we continue the study of 2‐colorings in hypergraphs. A hypergraph is 2‐colorable if there is a 2‐coloring of the vertices with no monochromatic hyperedge. Let denote the class of all k‐uniform k‐regular hypergraphs. It is known (see Alon and Bregman [Graphs Combin. 4 (1988) 303–306] and Thomassen [J. Amer. Math. Soc. 5 (1992), 217–229] that every hypergraph is 2‐colorable, provided . As remarked by Alon and Bregman the result is not true when , as may be seen by considering the Fano plane. Indeed there are several constructions for building infinite families of hypergraphs in that are not 2‐colorable. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set X of vertices in a hypergraph H to be a free set in H if we can 2‐color such that every edge in H receives at least one vertex of each color. We conjecture that for , every hypergraph has a free set of size in H. We show that the bound cannot be improved for any and we prove our conjecture when . Our proofs use results from areas such as transversal in hypergraphs, cycles in digraphs, and probabilistic arguments.     

A Doubling Construction for 3‐Uniform Friendship Hypergraphs with the Universal Pairs Property

In this note, we present a simple doubling construction for 3‐uniform friendship hypergraphs which generalizes the cubeconstructed hypergraphs from another study (L. Jørgensen and A. Sillasen, J Combin Designs (2014)). As a by‐product, we build point‐transitive 3‐uniform friendship hypergraphs of sizes and for all .     

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.     

Cycle Frames of Complete Multipartite Multigraphs ‐ III

For two graphs G and H their wreath product has vertex set in which two vertices and are adjacent whenever or and . Clearly, , where is an independent set on n vertices, is isomorphic to the complete m‐partite graph in which each partite set has exactly n vertices. A 2‐regular subgraph of the complete multipartite graph containing vertices of all but one partite set is called partial 2‐factor. For an integer λ, denotes a graph G with uniform edge multiplicity λ. Let J be a set of integers. If can be partitioned into edge‐disjoint partial 2‐factors consisting cycles of lengths from J, then we say that has a ‐cycle frame. In this paper, we show that for and , there exists a ‐cycle frame of if and only if and . In fact our results completely solve the existence of a ‐cycle frame of .     

The 1‐2‐3‐Conjecture for Hypergraphs

A weighting of the edges of a hypergraph is called vertex‐coloring if the weighted degrees of the vertices yield a proper coloring of the graph, i.e. every edge contains at least two vertices with different weighted degrees. In this article, we show that such a weighting is possible from the weight set for all hypergraphs with maximum edge size and not containing edges solely consisting of identical vertices. The number is best possible for this statement.     

The size of minimum 3‐trees

A 3‐uniform hypergraph (3‐graph) is said to be tight, if for any 3‐partition of its vertex set there is a transversal triple. We give the final steps in the proof of the conjecture that the minimum number of triples in a tight 3‐graph on n vertices is exactly . © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 103–114, 2007     

Squares of Hamiltonian cycles in 3‐uniform hypergraphs

We show that every 3‐uniform hypergraph H = (V,E) with |V(H)| = n and minimum pair degree at least (4/5 + o(1))n contains a squared Hamiltonian cycle. This may be regarded as a first step towards a hypergraph version of the Pósa‐Seymour conjecture.     

The Hamilton–Waterloo Problem for ‐Factors and ‐Factors

The Hamilton–Waterloo problem asks for a 2‐factorization of (for v odd) or minus a 1‐factor (for v even) into ‐factors and ‐factors. We completely solve the Hamilton–Waterloo problem in the case of C₃‐factors and ‐factors for .     

On the Hamilton‐Waterloo Problem for Bipartite 2‐Factors

Given two 2‐regular graphs F₁ and F₂, both of order n, the Hamilton‐Waterloo Problem for F₁ and F₂ asks for a factorization of the complete graph into α₁ copies of F₁, α₂ copies of F₂, and a 1‐factor if n is even, for all nonnegative integers α₁ and α₂ satisfying . We settle the Hamilton‐Waterloo Problem for all bipartite 2‐regular graphs F₁ and F₂ where F₁ can be obtained from F₂ by replacing each cycle with a bipartite 2‐regular graph of the same order.     

An Asymptotic Version of the Multigraph 1‐Factorization Conjecture

We give a self‐contained proof that for all positive integers r and all , there is an integer such that for all any regular multigraph of order 2n with multiplicity at most r and degree at least is 1‐factorizable. This generalizes results of Perkovi? and Reed (Discrete Math 165/166 (1997), 567–578) and Plantholt and Tipnis (J London Math Soc 44 (1991), 393–400).     

Enclosings of decompositions of complete multigraphs in 2‐factorizations

Let k, m, n, λ, and μ be positive integers. A decomposition of into edge‐disjoint subgraphs is said to be enclosed by a decomposition of into edge‐disjoint subgraphs if and, after a suitable labeling of the vertices in both graphs, is a subgraph of and is a subgraph of for all . In this paper, we continue the study of enclosings of given decompositions by decompositions that consist of spanning subgraphs. A decomposition of a graph is a 2‐factorization if each subgraph is 2‐regular and spanning, and is Hamiltonian if each subgraph is a Hamiltonian cycle. We give necessary and sufficient conditions for the existence of a 2‐factorization of that encloses a given decomposition of whenever and . We also give necessary and sufficient conditions for the existence of a Hamiltonian decomposition of that encloses a given decomposition of whenever and either or and , or , , and .     

Packing tight Hamilton cycles in 3‐uniform hypergraphs

Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ? H is a collection of n edges for which there is an ordering of the vertices v₁,…,v_n such that every triple of consecutive vertices {v_i,v_i+1,v_i+2} is an edge of C (indices are considered modulo n ). We develop new techniques which enable us to prove that under certain natural pseudo‐random conditions, almost all edges of H can be covered by edge‐disjoint tight Hamilton cycles, for n divisible by 4. Consequently, we derive the corollary that random 3‐uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo‐random digraphs with even numbers of vertices. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Hamilton cycle decomposition of 6‐regular circulants of odd order

The circulant G = C(n,S), where , is the graph with vertex set Z_n and edge set . It is shown that for n odd, every 6‐regular connected circulant C(n, S) is decomposable into Hamilton cycles. © 2006 Wiley Periodicals, Inc. J Combin Designs