skip to main content


Search for: All records

Award ID contains: 1700622

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Abstract

    For and , let be a ‐partite ‐graph with parts each of size , where is sufficiently large. Assume that for each , every ‐set in lies in at least edges, and . We show that if , then contains a matching of size . In particular, contains a matching of size if each crossing ‐set lies in at least edges, or each crossing ‐set lies in at least edges and . This special case answers a question of Rödl and Ruciński and was independently obtained by Lu, Wang, and Yu. The proof of Lu, Wang, and Yu closely follows the approach of Han by using the absorbing method and considering an extremal case. In contrast, our result is more general and its proof is thus more involved: it uses a more complex absorbing method and deals with two extremal cases.

     
    more » « less
  2. null (Ed.)
  3. null (Ed.)
    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. 
    more » « less
  4. 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. 
    more » « less
  5. 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$. 
    more » « less
  6. 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. 
    more » « less