Extremal problems on packing sparse graphs and hypergraphs

稀疏图和超图打包的极值问题

• 批准号: 0400498
• 负责人: Alexandr Kostochka
• 金额: $ 14.1万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-06-01 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0400498&HistoricalAwards=false
• 关键词: Extremal; problems; packing; sparse; graphs

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.

图和超图论中的许多基本问题都可以表述为打包问题。 如果所有这些图存在边不相交放置到完整的 K_n 图中，我们称 n 顶点图 G_1、G_2、... G_kpack 。 更一般地，如果所有这些图存在边不相交放置到完整的 r 均匀超图 K^r_n 中，则 n 顶点 r 均匀超图会打包。各种经典组合问题都可以建模为打包问题。例如，n 顶点图 G 中是否存在生成循环的问题是 n 循环是否与补集 G 打包的问题。 打包问题的另一个例子是图着色问题：图 G 是 k 可着色的当且仅当与由 k 个派系并集的图打包时。其他重要的打包主题还有子图存在问题、Ramsey 型问题和 Turan 型问题。 特别是，我们考虑公平着色、Ramsey 型问题、最小尺寸问题、图着色和 k 阶哈密顿图。当然，打包密集图比稀疏图更难。尽管如此，许多（超）图打包问题对于稀疏（超）图来说仍然重要且有趣。 稀疏性的自然度量是图的最大度。 另一个自然度量是其所有子图的最大平均度。 我们计划研究（超）图稀疏性的哪些限制意味着它们会打包。 除了一般的打包问题之外，我们还考虑需要较少稀疏性的特殊族中的图的打包。