On Subgraphs of Bounded Degeneracy in Hypergraphs

Kunal Dutta (1) , Arijit Ghosh (2)

1 DATASHAPE - Understanding the Shape of Data
2 Algorithms and Complexity

A k-uniform hypergraph is d-degenerate if every induced subgraph has a vertex of degree at most d. Given a k-uniform hyper-graph H = (V (H), E(H)), we show there exists an induced subgraph of size at least $v∈V (H) min (1, c_k d + (1/ d_H (v) + 1)^{1/(k−1)}$ , where $c_k = 2^{−(1+ 1/ k−1)}( 1 − 1/ k)$ and d_H (v) denotes the degree of ver-tex v in the hypergraph H. This connects, extends, and generalizes results of Alon-Kahn-Seymour (1987), on d-degenerate sets of graphs, Dutta-Mubayi-Subramanian (2012) on d-degenerate sets of linear hypergraphs, and Srinivasan-Shachnai (2004) on independent sets in hypergraphs to d-degenerate sub-graphs of hypergraphs. Our technique also gives optimal lower bounds for a more generalised definition of degeneracy introduced by Zaker (2013). We further give a simple non-probabilistic proof of the Dutta-Mubayi-Subramanian bound for linear k-uniform hypergraphs, which extends the Alon, Kahn and Seymour (1987) proof technique to hypergraphs. Finally we provide several applications in discrete geometry, extending results of Payne-Wood (2013) and Cardinal-Tóth-Wood (2016). We also address some natural algorithmic questions. The proof of our main theorem combines the random permutation technique of Bopanna-Caro-Wei and Beame and Luby, together with a new local density argument which may be of independent interest.

Domaines: Combinatoire [math.CO]; Géométrie algorithmique [cs.CG]

Kunal Dutta, Arijit Ghosh. On Subgraphs of Bounded Degeneracy in Hypergraphs. 2017. ⟨hal-01669886⟩