Reconsideration of Tangle and Ultrafilter using 
Separation and Partition

Takaaki Fujita

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

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

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

Reconsideration of Tangle and Ultrafilter using Separation and Partition

Takaaki Fujita

Received	Revised	Accepted	Published
18 May 2024	26 Jun 2024	11 Jul 2024	30 Jul 2024

Abstract

Tangle is a concept in graph theory that has a dual relationship with branch-width which is well-known graph width parameter. Ultrafilter, a fundamental notion in mathematics, is similarly known to have a dual relationship with branch-width when extended to a connectivity system (X, f). We will reconsider these concepts using separation and partition.

Keywords

Tangle, Linear tangle, branch-width, Filter, Ultrafilter.

References

[1] Reinhard Diestel, Christian Elbracht, and Raphael W. Jacobs, “Point Sets and Functions Inducing Tangles of Set Separations,” arXiv, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[2] Illya V. Hicks, and Boris Brimkov, “Tangle Bases: Revisited,” Networks: An International Journal, vol. 77, no. 1, pp. 161-172, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[3] Joseph E. Bonin, and Kevin Long, “Connectivity Gaps Among Matroids with the Same Enumerative Invariants,” Advances in Applied Mathematics, vol. 154, p. 102648, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[4] Vadim Lozin, and Igor Razgon, “Tree-width Dichotomy,” European Journal of Combinatorics, vol. 103, p. 103517, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[5] 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]
[6] Fedor V. Fomin, and Dimitrios M. Thilikos, “On the Monotonicity of Games Generated by Symmetric Submodular Functions,” Discrete Applied Mathematics, vol. 131, no. 2, pp. 323–335, 2003.
[CrossRef] [Google Scholar] [Publisher Link]
[7] Frank Gurski, and Robin Weishaupt, “The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations,” arXiv, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[8] P. Seymour, and R. Thomas, “Graph Searching and A Min-max Theorem for Tree-width,” Journal of Combinatorial Theory, Series B, vol. 58, no. 1, pp. 22-23, 1993.
[CrossRef] [Google Scholar] [Publisher Link]
[9] Isolde Adler, “Games for Width Parameters and Monotonicity,” arXiv, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[10] Jim Geelen et al., “Obstructions to Branch-decomposition of Matroids,” Journal of Combinatorial Theory, Series B, vol. 96, no. 4, pp. 560-570, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[11] Athanassios Koutsonas, Dimitrios M. Thilikos, and Koichi Yamazaki, “Outerplanar Obstructions for Matroid Pathwidth,” Discrete Mathematics, vol. 315-316, pp. 95-101, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[12] Christophe Paul, Evangelos Protopapas, and Dimitrios M. Thilikos, “Graph Parameters, Universal Obstructions, and WQO,” arXiv, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[13] Bruce A. Reed, “Tree Width and Tangles: A New Connectivity Measure and Some Applications,” Surveys in Combinatorics, vol. 241, pp. 87-162, 1997.
[Google Scholar]
[14] Jan Kurkofka, “Ends and Tangles, Stars and Combs, Minors and The Farey Graph,” PhD Thesis, Staats-und Universitätsbibliothek Hamburg Carl von Ossietzky, 2020.
[Google Scholar]
[15] Bogdan Alecu et al., “The Treewidth and Pathwidth of Graph Unions,” SIAM Journal on Discrete Mathematics, vol. 38, no. 1, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[16] Sandra Albrechtsen, “Refining Trees of Tangles in Abstract Separation Systems I: Inessential Parts,” arXiv preprint arXiv:2302.01808, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[17] 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]
[18] Fedor V. Fomin, and Tuukka Korhonen, “Fast FPT-approximation of Branchwidth,” Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 886-899, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[19] Mamadou Moustapha Kanté et al., “Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k,” Journal of Combinatorial Theory, Series B, vol. 160, pp. 15-35, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[20] Daniel Bienstock, “Graph Searching, Path-width, Tree-width and Related Problems (A Survey),” Reliability of Computer and Communication Networks, vol. 5 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 33-50, 1989.
[Google Scholar] [Publisher Link]
[21] Shoji Kasahara et al., “DAG-pathwidth: Graph Algorithmic Analyses of DAG-type Blockchain Networks,” IEICE TRANSACTIONS on Information and Systems, vol. E106, vol. 3, pp. 272-283, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Moran Feldman, “Maximizing Symmetric Submodular Functions,” ACM Transactions on Algorithms (TALG), vol. 13, no. 3, pp. 1-36, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[23] Maurice Queyranne, “Minimizing Symmetric Submodular Functions,” Mathematical Programming, vol. 82, pp. 3-12, 1998.
[CrossRef] [Google Scholar] [Publisher Link]
[24] 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]
[25] Eva Fluck, “Tangles and Hierarchical Clustering,” arXiv, vol. 38, no. 1, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[26] 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]
[27] Christian Elbracht, Jakob Kneip, Maximilian Teegen, “The Structure of Submodular Separation Systems,” arXiv, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[28] Reinhard Diestel, Fabian Hundertmark, and Sahar Lemanczyk, “Profiles of Separations: In Graphs, Matroids, and Beyond,” Combinatorica, vol. 39, pp. 37-75, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[29] Omid Amini et al., “Submodular Partition Functions,” Discrete Mathematics, vol. 309, no. 20, pp. 6000-6008, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[30] Petr Škoda, “Computability of Width of Submodular Partition Functions,” European Journal of Combinatorics, vol. 34, no. 3, pp. 660- 665, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[31] Henry H. Crapo, “Single-element Extensions of Matroids,” Journal of Research of the National Bureau of Standards-B, vol. 69B, no. 1- 2, pp. 55-65, 1965.
[Google Scholar]
[32] Masataka Nakamura, “A Single-element Extension of Antimatroids,” Discrete Applied Mathematics, vol. 120, no. 1-3, pp. 159-164, 2002.
[CrossRef] [Google Scholar] [Publisher Link]
[33] 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]
[34] Christophe Paul, Evangelos Protopapas, and Dimitrios M. Thilikos, “Universal Obstructions of Graph Parameters,” arXiv, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[35] Sang-il Oum, and Paul Seymour, “Certifying Large Branch-width,” Symposium on Discrete Algorithms: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, vol. 22, no. 26, pp. 810-813, 2006.
[Google Scholar]
[36] Costas D. Koutras, Christos Moyzes, and Christos Rantsoudis, “A Reconstruction of Default Conditionals within Epistemic Logic,” Proceedings of the Symposium on Applied Computing, pp. 977-982, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[37] Costas D. Koutras et al., “On Weak Filters and Ultrafilters: Set Theory From (and for) Knowledge Representation,” Logic Journal of the IGPL, vol. 31, no. 1, pp. 68-95, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[38] Emmanouil Lardas et al., “On Strict Brambles,” Graphs and Combinatorics, vol. 39, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[39] Dimitris Askounis, Costas D. Koutras, and Yorgos Zikos, “Knowledge Means ‘all’, Belief Means ‘most’,” Journal of Applied NonClassical Logics, vol. 26, no. 3, pp. 173-192, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[40] Shital Dilip Solanki, Ganesh Mundhe, and S.B. Dhotre, “Elementary Lift and Single Element Coextension of a Binary Gammoid,” arXiv, 2022.
[CrossRef] [Publisher Link]
[41] Joshua Erde, “A Bramble like Witness for Large Branch-Width,” arXiv, 2015.
[CrossRef] [Google Scholar] [Publisher Link]
[42] Isolde Adler, “Games for Width Parameters and Monotonicity,” arXiv, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[43] Martin Grohe, and Dániel Marx, “On Tree Width, Bramble Size, and Expansion,” Journal of Combinatorial Theory, Series B, vol. 99, no. 1, pp. 218-228, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[44] Hans L. Bodlaender, Alexander Grigoriev, and Arie M.C.A. Koster, “Treewidth Lower Bounds with Brambles,” Algorithmica, vol. 51, pp. 81-98, 2008.
[CrossRef] [Google Scholar] [Publisher Link]
[45] Daniel John Harvey, On Treewidth and Graph Minors, University of Melbourne, Department of Mathematics and Statistics, 2014.
[Google Scholar]
[46] William Wistar Comfort, and Stylianos Negrepontis, The Theory of Ultrafilters, Springer Science & Business Media, 2012.
[Google Scholar]
[47] David Booth, “Ultrafilters on a Countable Set,” Annals of Mathematical Logic, 1970.
[Google Scholar]
[48] Kenneth Kunen, “Ultrafilters and Independent Sets,” Transactions of the American Mathematical Society, vol. 172, pp. 299-306, 1972.
[Google Scholar] [Publisher Link]
[49] Philipp Eberenz. Characteristics of Profiles.
[50] Reinhard Diestel, Philipp Eberenz, and Joshua Erde, “Duality Theorems for Blocks and Tangles in Graphs,” SIAM Journal on Discrete Mathematics, vol. 31, no. 3, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[51] Reinhard Diestel, and Jakob Kneip, “Profinite Separation Systems,” Order, vol. 37, pp. 179-205, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[52] Talal Ali Al-Hawary, Matroid’s Filterbase, 2018.
[53] S.S. Kutateladze, “An Excursion into Set Theory,” Fundamentals of Functional Analysis, pp. 1-9, 1996.
[CrossRef] [Publisher Link]
[54] Ann-Kathrin Elm, and Hendrik Heine, “Limit-closed Profiles,” arXiv, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[55] Susumu Cato, “Quasi-decisiveness, Quasi-ultrafilter, and Social Quasi-orderings,” Social Choice and Welfare, vol. 41, pp. 169-202, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[56] Susumu Cato, “Quasi-stationary Social Welfare Functions,” Theory and Decision, vol. 89, pp. 85-106, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[57] Susumu Cato, “The Possibility of Paretian Anonymous Decision-making with an Infinite Population,” Social Choice and Welfare, vol. 53, pp. 587-601, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[58] Susumu Cato, “Social Choice, The Strong Pareto Principle, and Conditional Decisiveness,” Theory and Decision, vol. 75, pp. 563-579, 2013.
[CrossRef] [Google Scholar] [Publisher Link]

Citation :

Takaaki Fujita, "Reconsideration of Tangle and Ultrafilter using Separation and Partition," International Journal of Mathematics Trends and Technology (IJMTT), vol. 70, no. 7, pp. 5-12, 2024. Crossref, https://doi.org/10.14445/22315373/IJMTT-V70I7P102