# On Subgraphs of Bounded Degeneracy in Hypergraphs

1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 Algorithms and Complexity
MPII - Max-Planck-Institut für Informatik
Abstract : 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.
Type de document :
Pré-publication, Document de travail
2017
Domaine :

Littérature citée [22 références]

https://hal.archives-ouvertes.fr/hal-01669886
Contributeur : Kunal Dutta <>
Soumis le : jeudi 21 décembre 2017 - 07:26:37
Dernière modification le : jeudi 11 janvier 2018 - 16:38:51

### Fichier

Journal version.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01669886, version 1

### Citation

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

### Métriques

Consultations de la notice

## 34

Téléchargements de fichiers
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9442216753959656, "perplexity": 6508.708952317965}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-05/segments/1516084886895.18/warc/CC-MAIN-20180117102533-20180117122533-00611.warc.gz"}