On Subgraphs of Bounded Degeneracy in Hypergraphs

详细信息    查看全文

• 关键词：Degenerate graphs ; Independent sets ; Hypergraphs ; Random permutations
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9941
• 期：1
• 页码：295-306
• 全文大小：225 KB
• 参考文献：[AKS80]Ajtai, M., Komlós, J., Szemerédi, E.: A note on Ramsey numbers. J. Comb. Theory, Ser. A 29(3), 354–360 (1980)MathSciNet CrossRef MATH
  [AKS87]Alon, N., Kahn, J., Seymour, P.D.: Large induced degenerate subgraphs. Graphs Comb. 3(1), 203–211 (1987)MathSciNet CrossRef MATH
  [AS08]Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, Hoboken (2008)CrossRef MATH
  [BL90]Beame, P., Luby, M.: Parallel search for maximal independence given minimal dependence. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 212–218 (1990)
  [Car79]Caro, Y.: New results on the independence number. Technical report, Tel Aviv University (1979)
  [CT91]Caro, Y., Tuza, Z.: Improved lower bounds on k-independence. J. Graph Theory 15(1), 99–107 (1991)MathSciNet CrossRef MATH
  [DLR95]Duke, R.A., Lefmann, H., Rödl, V.: On uncrowded hypergraphs. Random Struct. Algorithms 6(2/3), 209–212 (1995)MathSciNet CrossRef MATH
  [DMS12]Dutta, K., Mubayi, D., Subramanian, C.R.: New lower bounds for the independence number of sparse graphs and hypergraphs. SIAM J. Discrete Math. 26(3), 1134–1147 (2012)MathSciNet CrossRef MATH
  [PP12]Pilipczuk, M., Pilipczuk, M.: Finding a maximum induced degenerate subgraph faster than 2\(^n\) . In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 3–12. Springer, Heidelberg (2012)CrossRef
  [PW13]Payne, M.S., Wood, D.R.: On the general position subset selection problem. SIAM J. Discrete Math. 27(4), 1727–1733 (2013)MathSciNet CrossRef MATH
  [She83]Shearer, J.B.: A note on the independence number of triangle-free graphs. Discrete Math. 46(1), 83–87 (1983)MathSciNet CrossRef MATH
  [She95]Shearer, J.B.: On the independence number of sparse graphs. Random Struct. Algorithms 7(3), 269–272 (1995)MathSciNet CrossRef MATH
  [Spe72]Spencer, J.H.: Turán’s theorem for k-graphs. Discrete Math. 2, 183–186 (1972)MathSciNet CrossRef MATH
  [SS04]Shachnai, H., Srinivasan, A.: Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18(3), 488–500 (2004)MathSciNet CrossRef MATH
  [ST83]Szemerédi, E., Trotter, W.T.: Extremal problems in discrete geometry. Combinatorica 3(3), 381–392 (1983)MathSciNet CrossRef MATH
  [Thi99]Thiele, T.: A lower bound on the independence number of arbitrary hypergraphs. J. Graph Theory 30(3), 213–221 (1999)MathSciNet CrossRef MATH
  [Tur41]Turán, P.: On an extremal problem in graph theory. Math. Fiz. Lapok 48, 436–452 (1941). (in Hungarian)
  [Wei81]Wei, V.K.: A lower bound on the stability number of a simple graph. Technical Memorandum TM 81-11217-9, Bell Laboratories (1981)
  [Zak13]Zaker, M.: Generalized degeneracy, dynamic monopolies, maximum degenerate subgraphs. Discrete Appl. Math. 161(1617), 2716–2723 (2013)MathSciNet CrossRef MATH
  
• 作者单位：Kunal Dutta (14)
  Arijit Ghosh (15)
  
  14. DataShape, Inria Sophia Antipolis – Méditerranée, Méditerranée, France
  15. ACM Unit, Indian Statistical Institute, Kolkata, India
  
• 丛书名：Graph-Theoretic Concepts in Computer Science
• ISBN：978-3-662-53536-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9941

文摘

A k-uniform hypergraph has degeneracy bounded by d if every induced subgraph has a vertex of degree at most d. Given a k-uniform hypergraph \(H=(V(H), E(H))\), we show there exists an induced subgraph of size at least $$\begin{aligned} \sum _{v \in V(H)} \min \left\{ 1, \, c_{k}\, \left( \frac{d+1}{d_{H} (v)+1}\right) ^{1/(k-1)} \right\} , \end{aligned}$$where \(c_{k} = 2^{- \left( 1 + \frac{1}{k-1} \right) }\left( 1-\frac{1}{k}\right) \) and \(d_{H}(v)\) denotes the degree of vertex v in the hypergraph H. This extends and generalizes a result of Alon-Kahn-Seymour (Graphs and Combinatorics, 1987) for graphs, as well as a result of Dutta-Mubayi-Subramanian (SIAM Journal on Discrete Mathematics, 2012) for linear hypergraphs, to general k-uniform hypergraphs. We also generalize the results of Srinivasan and Shachnai (SIAM Journal on Discrete Mathematics, 2004) from independent sets (0-degenerate subgraphs) to d-degenerate subgraphs. We further give a simple non-probabilistic proof of the Dutta-Mubayi-Subramanian bound for linear k-uniform hypergraphs, which extends the Alon-Kahn-Seymour (Graphs and Combinatorics, 1987) proof technique to hypergraphs. Our proof combines the random permutation technique of Bopanna-Caro-Wei (see e.g. The Probabilistic Method, N. Alon and J. H. Spencer; Dutta-Mubayi-Subramanian) and also Beame-Luby (SODA, 1990) together with a new local density argument which may be of independent interest. We also provide some applications in discrete geometry, and address some natural algorithmic questions. Keywords Degenerate graphs Independent sets Hypergraphs Random permutations Page %P Close Plain text Look Inside Chapter Metrics Provided by Bookmetrix Reference tools Export citation EndNote (.ENW) JabRef (.BIB) Mendeley (.BIB) Papers (.RIS) Zotero (.RIS) BibTeX (.BIB) Add to Papers Other actions About this Book Reprints and Permissions Share Share this content on Facebook Share this content on Twitter Share this content on LinkedIn Supplementary Material (0) References (19) References[AKS80]Ajtai, M., Komlós, J., Szemerédi, E.: A note on Ramsey numbers. J. Comb. Theory, Ser. A 29(3), 354–360 (1980)MathSciNetCrossRefMATH[AKS87]Alon, N., Kahn, J., Seymour, P.D.: Large induced degenerate subgraphs. Graphs Comb. 3(1), 203–211 (1987)MathSciNetCrossRefMATH[AS08]Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, Hoboken (2008)CrossRefMATH[BL90]Beame, P., Luby, M.: Parallel search for maximal independence given minimal dependence. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 212–218 (1990)[Car79]Caro, Y.: New results on the independence number. Technical report, Tel Aviv University (1979)[CT91]Caro, Y., Tuza, Z.: Improved lower bounds on k-independence. J. Graph Theory 15(1), 99–107 (1991)MathSciNetCrossRefMATH[DLR95]Duke, R.A., Lefmann, H., Rödl, V.: On uncrowded hypergraphs. Random Struct. Algorithms 6(2/3), 209–212 (1995)MathSciNetCrossRefMATH[DMS12]Dutta, K., Mubayi, D., Subramanian, C.R.: New lower bounds for the independence number of sparse graphs and hypergraphs. SIAM J. Discrete Math. 26(3), 1134–1147 (2012)MathSciNetCrossRefMATH[PP12]Pilipczuk, M., Pilipczuk, M.: Finding a maximum induced degenerate subgraph faster than 2\(^n\). In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 3–12. Springer, Heidelberg (2012)CrossRef[PW13]Payne, M.S., Wood, D.R.: On the general position subset selection problem. SIAM J. Discrete Math. 27(4), 1727–1733 (2013)MathSciNetCrossRefMATH[She83]Shearer, J.B.: A note on the independence number of triangle-free graphs. Discrete Math. 46(1), 83–87 (1983)MathSciNetCrossRefMATH[She95]Shearer, J.B.: On the independence number of sparse graphs. Random Struct. Algorithms 7(3), 269–272 (1995)MathSciNetCrossRefMATH[Spe72]Spencer, J.H.: Turán’s theorem for k-graphs. Discrete Math. 2, 183–186 (1972)MathSciNetCrossRefMATH[SS04]Shachnai, H., Srinivasan, A.: Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18(3), 488–500 (2004)MathSciNetCrossRefMATH[ST83]Szemerédi, E., Trotter, W.T.: Extremal problems in discrete geometry. Combinatorica 3(3), 381–392 (1983)MathSciNetCrossRefMATH[Thi99]Thiele, T.: A lower bound on the independence number of arbitrary hypergraphs. J. Graph Theory 30(3), 213–221 (1999)MathSciNetCrossRefMATH[Tur41]Turán, P.: On an extremal problem in graph theory. Math. Fiz. Lapok 48, 436–452 (1941). (in Hungarian)[Wei81]Wei, V.K.: A lower bound on the stability number of a simple graph. Technical Memorandum TM 81-11217-9, Bell Laboratories (1981)[Zak13]Zaker, M.: Generalized degeneracy, dynamic monopolies, maximum degenerate subgraphs. Discrete Appl. Math. 161(1617), 2716–2723 (2013)MathSciNetCrossRefMATH About this Chapter Title On Subgraphs of Bounded Degeneracy in Hypergraphs Book Title Graph-Theoretic Concepts in Computer Science Book Subtitle 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers Pages pp 295-306 Copyright 2016 DOI 10.1007/978-3-662-53536-3_25 Print ISBN 978-3-662-53535-6 Online ISBN 978-3-662-53536-3 Series Title Lecture Notes in Computer Science Series Volume 9941 Series ISSN 0302-9743 Publisher Springer Berlin Heidelberg Copyright Holder Springer-Verlag GmbH Germany Additional Links About this Book Topics Discrete Mathematics in Computer Science Algorithm Analysis and Problem Complexity Data Structures Computer Graphics Geometry Algorithms Keywords Degenerate graphs Independent sets Hypergraphs Random permutations Industry Sectors Engineering Biotechnology Pharma eBook Packages Computer Science Editors Pinar Heggernes (13) Editor Affiliations 13. University of Bergen Authors Kunal Dutta (14) Arijit Ghosh (15) Author Affiliations 14. DataShape, Inria Sophia Antipolis – Méditerranée, Méditerranée, France 15. ACM Unit, Indian Statistical Institute, Kolkata, India Continue reading... To view the rest of this content please follow the download PDF link above.