d-matching in 3-uniform hypergraphs

A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. A $d$-matching in a 3-uniform hypergraph $H$ is a matching of size $d$. Let $V_1,V_2$ be a partition of $n$ vertices such that $\left|V_1\right|=2d?1$ and $\left|V_2\right|=n?2d+1$. Denote by $E_3(2d?1,n?2d+1)$ the 3-uniform hypergraph with vertex set $V_1\cup V_2$ consisting of all those edges which contain at least two vertices of $V_1$. Let $H$ be a 3-uniform hypergraph of order $n\ge 9d^2$ such that $deg\left(u\right)+deg\left(v\right)>2\left[\left(\genfrac{}{}{0ex}{}{n?1}{2}\right)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)\right]$ for any two adjacent vertices $u,v\in V\left(H\right)$. In this paper, we prove $H$ contains a $d$-matching if and only if $H$ is not a subgraph of $E_3(2d?1,n?2d+1)$.     

Partitioning 3-uniform hypergraphs

Bollobás and Thomason conjectured that the vertices of any r-uniform hypergraph with m edges can be partitioned into r sets so that each set meets at least rm/(2r−1) edges. For r=3, Bollobás, Reed and Thomason proved the lower bound (1−1/e)m/3≈0.21m, which was improved to (5/9)m by Bollobás and Scott and to 0.6m by Haslegrave. In this paper, we show that any 3-uniform hypergraph with m edges can be partitioned into 3 sets, each of which meets at least 0.65m−o(m) edges.     

The size of 3-uniform hypergraphs with given matching number and codegree

To determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvátal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear 3-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of 3-graphs with bounded codegree and matching number.     

Edge intersection graphs of linear 3-uniform hypergraphs

Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class is NP-complete. We prove that this problem is polynomially solvable in the class of graphs with minimum vertex degree ≥10. It is also proved that the class is characterized by a finite list of forbidden induced subgraphs in the class of graphs with minimum vertex degree ≥16.     

On the number of minimal transversals in 3-uniform hypergraphs

We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cⁿ, where c≈1.6702. The best known lower bound for this number, due to Tomescu, is adⁿ, where d=10^1/5≈1.5849 and a is a constant.     

Decompositions of the 3-uniform hypergraphs K(3)v into hypergraphs of a certain type

In this paper, we investigate a generalization of graph decomposition, called hypergraph decomposition. We show that a decomposition of a 3-uniform hypergraph K(3)v into a special kind of hypergraph K(3)4 - e exists if and only if v ≡ 0, 1, 2 (mod 9) and v ≥ 9.     

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

超图H=(V,E)顶点集为V,边集为E.S(C)V是H的顶点子集,如果HS不含有圈,则称S是H的点反馈数,记tc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则tc(H)≤m/3;(ii)如果日是3-一致超图,边数为m,则Tc(H)≤m/2并且等式成立当且仅当日任何一个连通分支是孤立...     

The existence of regular self-complementary 3-uniform hypergraphs

A k-uniform hypergraph with vertex set V and edge set E is called t-subset-regular if every t-element subset of V lies in the same number of elements of E. In this paper we show that a 1-subset-regular self-complementary 3-uniform hypergraph with n vertices exists if and only if n≥5 and n is congruent to 1 or 2 modulo 4.     

Saturation of Berge hypergraphs

Given a graph $F$, a hypergraph is a Berge- $F$ if it can be obtained by expanding each edge in $F$ to a hyperedge containing it. A hypergraph $H$ is Berge-$F$-saturated if $H$ does not contain a subhypergraph that is a Berge-$F$, but for any edge $e\in E\left(\overline{H}\right)$, $H+e$ does. The $k$-uniform saturation number of Berge-$F$ is the minimum number of edges in a $k$-uniform Berge-$F$-saturated hypergraph on $n$ vertices. For $k=2$ this definition coincides with the classical definition of saturation for graphs. In this paper we study the saturation numbers for Berge triangles, paths, cycles, stars and matchings in $k$-uniform hypergraphs.     

Bounds for the Graham–Pollak theorem for hypergraphs

Let $f_r\left(n\right)$ represent the minimum number of complete $r$-partite $r$-graphs required to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. The Graham–Pollak theorem states that $f_2\left(n\right)=n?1$. An upper bound of $(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was known. Recently this was improved to $\frac{14}{15}(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ for even $r\ge 4$. A bound of $\left[\frac{r}{2}{\left(\frac{14}{15}\right)}^{\frac{r}{4}}+o\left(1\right)\right](1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was also proved recently. Let $c_r$ be the limit of $\frac{f_r\left(n\right)}{\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)}$ as $n\to \infty$. The smallest odd $r$ for which $c_r<1$ that was known was for $r=295$. In this note we improve this to $c_{113}<1$ and also give better upper bounds for $f_r\left(n\right)$, for small values of even $r$.     

Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs

In this paper, we continue our study of 2-colorings in hypergraphs (see, Henning and Yeo, 2013). A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen, 1992) that every 4-uniform 4-regular hypergraph is 2-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph $H$ to be a free vertex in $H$ if we can 2-color $V\left(H\right)?\left\{v\right\}$ such that every hyperedge in $H$ contains vertices of both colors (where $v$ has no color). We prove that every 4-uniform 4-regular hypergraph has a free vertex. This proves a conjecture in Henning and Yeo (2015). Our proofs use a new result on not-all-equal 3-SAT which is also proved in this paper and is of interest in its own right.     

Large monochromatic components in colorings of complete 3-uniform hypergraphs

Let f(n,r) be the largest integer m with the following property: if the edges of the complete 3-uniform hypergraph are colored with r colors then there is a monochromatic component with at least m vertices. Here we show that and . Both results are sharp under suitable divisibility conditions (namely if n is divisible by 7, or by 6 respectively).     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.     

Dirac-type conditions for hamiltonian paths and cycles in 3-uniform hypergraphs

A hamiltonian path (cycle) in an n-vertex 3-uniform hypergraph is a (cyclic) ordering of the vertices in which every three consecutive vertices form an edge. For large n, we prove an analog of the celebrated Dirac theorem for graphs: there exists n₀ such that every n-vertex 3-uniform hypergraph H, n?n₀, in which each pair of vertices belongs to at least n/2−1 (⌊n/2⌋) edges, contains a hamiltonian path (cycle, respectively). Both results are easily seen to be optimal.     

Hamiltonian chains in hypergraphs

A cyclic ordering of the vertices of a k‐uniform hypergraph is called a hamiltonian chain if any k consecutive vertices in the ordering form an edge. For k = 2 this is the same as a hamiltonian cycle. We consider several natural questions about the new notion. The main result is a Dirac‐type theorem that provides a sufficient condition for finding hamiltonian chains in k‐uniform hypergraphs with large (k − 1)‐minimal degree. If it is more than than the hypergraph contains a hamiltonian chain. © 1999 Wiley & Sons, Inc. J Graph Theory 30: 205–212, 1999     

Characterizations of graphs G having all [1,k]-factors in kG

Let $k\ge 1$ be an integer and $G$ be a graph. Let $kG$ denote the graph obtained from $G$ by replacing each edge of $G$ with $k$ parallel edges. We say that $G$ has all $[1,k]$-factors or all fractional $[1,k]$-factors if $G$ has an $h$-factor or a fractional $h$-factor for every function $h:V\left(G\right)\to \{1,2,\dots ,k\}$ with $h\left(V\left(G\right)\right)$ even. In this note, we come up with simple characterizations of a graph $G$ such that $kG$ has all $[1,k]$-factors or all fractional $[1,k]$-factors. These characterizations are extensions of Tutte’s 1-Factor Theorem and Tutte’s Fractional 1-Factor Theorem.