Extremal problems on packing sparse graphs and hypergraphs

图论和超图论中的许多基本问题都可以用包装问题来表述。我们说n顶点图G_1， G_2，…G_kpack，如果所有这些图都有一个不相交的边放置到完整的K_n图中。更一般地说，n顶点的r-均匀超图，如果存在一个边不相交的位置，那么所有这些图都组合成完整的r-均匀超图K^r_n。各种经典的组合问题都可以建模为包装问题。例如，n顶点图G上是否存在生成环的问题是n环是否与补G包在一起的问题。另一个装箱问题的例子是图着色问题：图G是k色的当且仅当装箱的图是k个团的并集。其他重要的分组问题还有子图存在性问题、ramsey型问题和turan型问题。特别地，我们考虑了公平着色、ramsey型问题、最小尺寸问题、图着色和k阶哈密顿图。当然，填充密集图比填充稀疏图更难。然而，对于稀疏（超）图来说，许多（超）图打包问题仍然是重要和有趣的。稀疏性的一个自然度量是图的最大程度。另一个自然度量是所有子图的最大平均度。我们计划研究对（超）图的稀疏性的限制意味着它们是打包的。除了一般的装箱问题外，我们还考虑了特殊族图的装箱问题，在这种情况下，图的稀疏性要求较低。

Many basic questions in graph and hypergraph theory can be phrased aspacking problems. We say that n-vertex graphs G_1, G_2, ... G_kpack if there is an edge disjoint placement of all these graphs into the complete K_n graph . More generally, n-vertex r-uniform hypergraphs pack if there exists an edge disjoint placement ofall these graphs into the complete r-uniform hypergraph K^r_n.Various classical combinatorial problems can be modeled as packing problems.For example, the problem of existence of a spanning cycle in an n-vertexgraph G is the question whether the n-cycle packs with the complement G . Another example of a packing problem is the graph coloring problem: A graph G is k-colorable if and only if packs with a graph that is the union of k cliques. Other important packing topics are also subgraph existence problems, Ramsey-type problems, and Turan-type problems. In particular, we consider equitable colorings,Ramsey-type problems, minimum size problems, graph colorings, andk-ordered Hamiltonian graphs.Certainly, it is harder to pack dense graphs than sparse ones.Nevertheless, many (hyper)graph packing problems remain important andinteresting for sparse (hyper)graphs. A natural measure of sparseness is the maximum degree of a graph. Another natural measure is the maximum average degree over all of its subgraphs. We plan to study what restrictions on sparseness of (hyper)graphs imply that they pack. In addition to the general packing problem, we consider packings of graphs in special families where less sparseness is needed.