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     

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      

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).     

Detachments of Amalgamated 3‐Uniform Hypergraphs Factorization Consequences

A is a hypergraph obtained from by splitting some or all of its vertices into more than one vertex. Amalgamating a hypergraph can be thought of as taking , partitioning its vertices, then for each element of the partition squashing the vertices to form a single vertex in the amalgamated hypergraph . In this paper, we use Nash‐Williams lemma on laminar families to prove a detachment theorem for amalgamated 3‐uniform hypergraphs, which yields a substantial generalization of previous amalgamation theorems by Hilton, Rodger, and Nash‐Williams. To demonstrate the power of our detachment theorem, we show that the complete 3‐uniform n‐partite multihypergraph can be expressed as the union of k edge‐disjoint factors, where for , is ‐regular, if and only if:

1. for all ,
2. for each i, , and
3. .

     

A note on 3‐partite graphs without 4‐cycles

Let $C_4$ be a cycle of order 4. Write $ex\left(n,n,n,C_4\right)$ for the maximum number of edges in a balanced 3‐partite graph whose vertex set consists of three parts, each has $n$ vertices that have no subgraph isomorphic to $C_4$. In this paper, we show that $ex\left(n,n,n,C_4\right)\ge \frac{3}{2}n\left(p+1\right)$, where $n=\frac{p\left(p?1\right)}{2}$ and $p$ is a prime number. Note that $ex\left(n,n,n,C_4\right)\le \left(\frac{3\sqrt{2}}{2}+o\left(1\right)\right)n^{\frac{3}{2}}$ from Tait and Timmons's works. Since for every integer $m$, one can find a prime $p$ such that $m\le p\le \left(1+o\left(1\right)\right)m$, we obtain that $\underset{n\to \infty }{\lim }\frac{ex\left(n,n,n,C_4\right)}{\frac{3\sqrt{2}}{2}{n}^{\frac{3}{2}}}=1$.     

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.     

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 .     

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.     

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.     

Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three

In this paper, we study lower bounds on the size of a maximum independent set and a maximum matching in a hypergraph of rank three. The rank in a hypergraph is the size of a maximum edge in the hypergraph. A hypergraph is simple if no two edges contain exactly the same vertices. Let H be a hypergraph and let and be the size of a maximum independent set and a maximum matching, respectively, in H, where a set of vertices in H is independent (also called strongly independent in the literature) if no two vertices in the set belong to a common edge. Let H be a hypergraph of rank at most three and maximum degree at most three. We show that with equality if and only if H is the Fano plane. In fact, we show that if H is connected and different from the Fano plane, then and we characterize the hypergraphs achieving equality in this bound. Using this result, we show that that if H is a simple connected 3‐uniform hypergraph of order at least 8 and with maximum degree at most three, then and there is a connected 3‐uniform hypergraph H of order 19 achieving this lower bound. Finally, we show that if H is a connected hypergraph of rank at most three that is not a complete hypergraph on vertices, where denotes the maximum degree in H, then and this bound is asymptotically best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory     

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.     

On effective σ‐boundedness and σ‐compactness

We prove several dichotomy theorems which extend some known results on σ‐bounded and σ‐compact pointsets. In particular we show that, given a finite number of $\Delta ^{1}_{1}$ equivalence relations $\mathrel {\mathsf {F}}_1,\dots ,\mathrel {\mathsf {F}}_n$, any $\Sigma ^{1}_{1}$ set A of the Baire space either is covered by compact $\Delta ^{1}_{1}$ sets and lightface $\Delta ^{1}_{1}$ equivalence classes of the relations $\mathrel {\mathsf {F}}_i$, or A contains a superperfect subset which is pairwise $\mathrel {\mathsf {F}}_i$‐inequivalent for all i = 1, …, n. Further generalizations to $\Sigma ^{1}_{2}$ sets A are obtained.     

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     

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     

σ‐short Boolean algebras

We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach‐Mazur Boolean game. A σ‐short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ‐short Boolean algebras and study properties of σ‐short Boolean algebras. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Large ‐ or ‐Minors in 3‐Connected Graphs

There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003