skip to main content

Title: Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles
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.
; ;
Award ID(s):
Publication Date:
Journal Name:
Combinatorics, Probability and Computing
Page Range or eLocation-ID:
840 to 870
Sponsoring Org:
National Science Foundation
More Like this
  1. We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max  uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log  n )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our resultmore »for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.« less
  2. Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $H$ in an $n$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $H$ and the number of all subgraphs with the same number vertices as $H$; this quantity is known as the _inducibility_ of $H$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $k$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $k$ vertices be? Fix $k$, consider a graph with $n$ vertices join each pair of vertices independently by an edge with probability $\binom{k}{2}^{-1}$. The expected number of $k$-vertex induced subgraphs with exactly one edge is $e^{-1}+o(1)$. So, the inducibility of large graphs with a single edge is at least $e^{-1}+o(1)$. This article establishes that this bound ismore »the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $k$-vertex graphs with exactly $l$ edges where $0« less
  3. In the k -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger and Stein can solve this in roughly O ( n 2k ) time. However, lower bounds from conjectures about the k -clique problem imply that Ω ( n (1- o (1)) k ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k -cut in n 1.98k + O(1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed k -cut of weight α λ k with probability Ω k ( n - α k ), where λ k denotes the minimum k -cut weight. This also gives an extremal bound of O k ( n k ) on the number of minimum k -cuts and an algorithm to compute λ k with roughly n k polylog( n ) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardnessmore »of max-weight k -clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 λ k / k , using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—in the Karger process.« less
  4. 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.
  5. Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V, E) with edge costs c ∈ ℝ_{≥ 0}^E, a root r ∈ V and k terminals K ⊆ V, we need to output a minimum-cost arborescence in G that contains an rrightarrow t path for every t ∈ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O(log²k/log log k)-approximation algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound d_v on each vertex v ∈ V, and we require that every vertex v in the output tree has at most d_v children. We give a quasi-polynomial time (O(log n log k), O(log² n))-bicriteria approximation: The algorithm produces a solution with cost at most O(log nlog k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O(log²n). This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O(log²n) is an O(logmore »n)-factor away from the approximation lower bound of Ω(log n) from the Set Cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an (O(log nlog k), O(log n))-bicriteria approximation algorithm for DB-GST-T.« less