Extremal problems on packing sparse graphs and hypergraphs

图和超图理论中的许多基本问题都可以归结为短语问题。我们称n-顶点图G_1，G_2，…G_kpack如果所有这些图在完全K_n图中都有边不相交的放置。更一般地，n-点r-一致超图在完全r-一致超图K^r_n中存在边不相交的位置时是填充的。各种经典的组合问题可以被建模为填充问题。例如，n-点r-一致超图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.