Extremal problems on packing sparse graphs and hypergraphs

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Many basic questions in graph and hypergraph theory can be phrased as packing problems. We say that n-vertex graphs G_1, G_2, ... G_k pack 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-vertex graph 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, and k-ordered Hamiltonian graphs. Certainly, it is harder to pack dense graphs than sparse ones. Nevertheless, many (hyper)graph packing problems remain important and interesting 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.