Search for: All records

Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 

Abstract Given two k -graphs ( k -uniform hypergraphs) F and H , a perfect F -tiling (or F -factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H . For all complete k -partite k -graphs K , Mycroft proved a minimum codegree condition that guarantees a K -factor in an n -vertex k -graph, which is tight up to an error term o ( n ). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K (k) (1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively. 

Let $n, s$ be positive integers such that $$n$$ is sufficiently large and $$s\le n/3$$. Suppose $$H$$ is a 3-uniform hypergraph of order $$n$$ without isolated vertices. If $$\deg(u)+\deg(v) > 2(s-1)(n-1)$$ for any two vertices $$u$$ and $$v$$ that are contained in some edge of $$H$$, then $$H$$ contains a matching of size $$s$$. This degree sum condition is best possible and confirms a conjecture of the authors [Electron. J. Combin. 25 (3), 2018], who proved the case when $s= n/3$. 

We determine the minimum degree sum of two adjacent vertices that ensures a perfect matching in a 3-uniform hypergraph without isolated vertex. Suppose that $$H$$ is a 3-uniform hypergraph whose order $$n$$ is sufficiently large and divisible by $$3$$. If $$H$$ contains no isolated vertex and $$\deg(u)+\deg(v) > \frac{2}{3}n^2-\frac{8}{3}n+2$$ for any two vertices $$u$$ and $$v$$ that are contained in some edge of $$H$$, then $$H$$ contains a perfect matching. This bound is tight and the (unique) extremal hyergraph is a different \emph{space barrier} from the one for the corresponding Dirac problem.