A Short Note of the Relationship between Loose Tangles 
and Filters

Takaaki Fujita

doi:https://doi.org/10.14445/22315373/IJMTT-V70I7P101

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 70 | Issue 7 | Year 2024 | Article Id. IJMTT-V70I7P101 | DOI : https://doi.org/10.14445/22315373/IJMTT-V70I7P101

A Short Note of the Relationship between Loose Tangles and Filters

Takaaki Fujita

Received	Revised	Accepted	Published
16 May 2024	25 Jun 2024	09 Jul 2024	30 Jul 2024

Abstract

Tangle, a concept related to graph width parameters, has been defined and studied in graph theory. It has a dual relationship with branch width. Loose Tangle relaxes the axioms of Tangle and also holds significance in research. Filters, defined based on symmetric submodular functions, are related to Tangles. This short paper aims to establish the cryptomorphism between Loose Tangle and filter.

Keywords

Tangle, Loose tangle, Filter.

References

[1] Neil Robertson, and Paul D Seymour, “Graph Minors. X. Obstructions to Tree-decomposition,” Journal of Combinatorial Theory, Series B, vol. 52, no. 2, pp. 153–190, 1991.
[CrossRef] [Google Scholar] [Publisher Link]
[2] Daniel Bienstock, “Graph Searching, Path-width, Tree-width and Related Problems (A Survey),” Reliability of Computer and Communication Networks, pp. 33–50, 1989.
[Google Scholar]
[3] Martin Grohe, “Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles),” arXiv, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[4] Bruce Reed, “Tree Width and Tangles: A New Connectivity Measure and Some Applications,” Surveys in Combinatorics, vol. 241, pp. 87–162, 1997.
[Google Scholar]
[5] Jakob Kneip, “Ends as Tangles,” arXiv, 2015.
[CrossRef] [Google Scholar] [Publisher Link]
[6] Takkaki Fujita, and Koichi Yamazaki, “Equivalence Between Linear Tangle and Maximal Single Ideal,” Open Journal of Discrete Mathematics, vol. 9, no. 1, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[7] Sang-il Oum, and Paul Seymour, “Testing Branch-width,” Journal of Combinatorial Theory, Series B, vol. 97, no. 3, pp. 385–393, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Christian Elbracht, Jakob Kneip, and Maximilian Teegen, “Obtaining Trees of Tangles from Tangle-tree Duality,” arXiv, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[9] Jim Geelen, Bert Gerards, and Geoff Whittle, “Tangles, Tree-decompositions and Grids in Matroids,” Journal of Combinatorial Theory, Series B, vol. 99, no. 4, pp. 657-667, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[10] Reinhard Diestel, “Ends and Tangles,” Abhandlungen Aus Dem Mathematischen Seminar Der Universität Hamburg, vol. 87, pp. 223- 244, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[11] Dan Bienstock et al., “Quickly Excluding a Forest,” Journal on Combinatorial Theory, Series B, vol. 52, pp. 274-283, 1991.
[Google Scholar]
[12] Eva Fluck, “Tangles and Hierarchical Clustering,” SIAM Journal on Discrete Mathematics, vol. 38, no. 1, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[13] Benjamin Merlin Bumpus, Kitty Meeks, and William Pettersson, “Directed Branch-width: A Directed Analogue of Tree-width,” arXiv, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Reinhard Diestel, and Sang-il Oum, “Tangle-tree Duality in Abstract Separation Systems,” Advances in Mathematics, vol. 377, p. 107470, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Reinhard Diestel, “Graph Minors I: A Short Proof of the Path-width Theorem,” Combinatorics, Probability and Computing, vol. 4, no. 1, pp. 27-30, 1995.
[CrossRef] [Google Scholar] [Publisher Link]
[16] Reinhard Diestel, and Sang-il Oum, “Tangle-tree Duality: In Graphs, Matroids and Beyond,” Combinatorica, vol. 39, pp. 879-910, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[17] Archontia C. Giannopoulou et al., “Directed Tangle Tree-Decompositions and Applications,” Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 377-405, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[18] Omid Amini et al., “Submodular Partition Functions,” Discrete Mathematics, vol. 309, no. 20, pp. 6000-6008, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[19] Janne Korhonen, and Pekka Parviainen, “Exact Learning of Bounded Tree-width Bayesian Networks,” Proceedings of the Sixteen International Conference on Artificial Intelligence and Statistics, vol. 31, pp. 370-378, 2013.
[Google Scholar] [Publisher Link]
[20] David R. Karger, and Nathan Srebro, Learning Markov Networks: Maximum Bounded Tree-width Graphs, SODA, 2001.
[Google Scholar]
[21] Reinhard Diestel, “Tangles in the Social Sciences,” arXiv, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Pekka Parviainen, Hossein Shahrabi Farahani, and Jens Lagergren, “Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming,” Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, vol. 33, pp. 751- 759, 2014.
[Google Scholar] [Publisher Link]
[23] Fedor V. Fomin, “Pathwidth of Planar and Line Graphs,” Graphs and Combinatorics, vol. 19, pp. 91-99, 2003.
[CrossRef] [Publisher Link]
[24] Rhiannon Hall et al., “On Matroids of Branch-width Three,” Journal of Combinatorial Theory, Series B, vol. 86, no. 1, pp. 148-171, 2002.
[CrossRef] [Google Scholar] [Publisher Link]
[25] Illya V. Hicks, “Graphs, Branchwidth, and Tangles! Oh My!,” Networks: An International Journal, vol. 45, no. 2, pp. 55-60, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[26] Mohammad Ali Safari, “D-width: A More Natural Measure for Directed Tree Width,” Mathematical Foundations of Computer Science 2005, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[27] Jan Kurkofka, “Ends and Tangles, Stars and Combs, Minors and The Farey Graph,” Dissertation, Staats-und Universitätsbibliothek Hamburg Carl von Ossietzky, 2020.
[Google Scholar]
[28] Jan Kurkofka, “On the Tangle Compactification of Infinite Graphs,” arXiv, 2019.
[CrossRef] [Google Scholar] [Publisher Link]

Citation :

Takaaki Fujita, "A Short Note of the Relationship between Loose Tangles and Filters," International Journal of Mathematics Trends and Technology (IJMTT), vol. 70, no. 7, pp. 1-4, 2024. Crossref, https://doi.org/10.14445/22315373/IJMTT-V70I7P101