Quasi-Ultrafilter on the Connectivity System: Its 
Relationship to Branch-Decomposition

Takaaki Fujita

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

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

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

Quasi-Ultrafilter on the Connectivity System: Its Relationship to Branch-Decomposition

Takaaki Fujita

Received	Revised	Accepted	Published
14 Jan 2024	25 Feb 2024	14 Apr 2024	30 Mar 2024

Abstract

The exploration of graph width parameters, spanning both graph theory and algebraic frameworks, has captured substantial attention. Among these, branch width has distinctly emerged as a key metric. The Quasi-Ultrafilter serves as an axiomatic tool for scrutinizing incomplete social judgments. In this concise study, we outline a coherent definition of Quasi Ultrafilters within the connectivity system and clarify its dual association with branch width.

Keywords

Filter, Ultrafilter, Quasi-Ultrafilter, Branch-width, Branch-decomposition.

References

[1] 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]
[2] Susumu Cato, “Quasi-Stationary Social Welfare Functions,” Theory and Decision, vol. 89, no. 1, pp. 85–106, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[3] Susumu Cato, “The Possibility of Paretian Anonymous Decision-Making with an Infinite Population,” Social Choice and Welfare, vol. 53, no. 4, pp. 587–601, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[4] 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]
[5] Walter Bossert, and Susumu Cato, “Superset-Robust Collective Choice Rules,” Mathematical Social Sciences, vol. 109, pp. 126–136, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[6] Shino Takayama, and Akira Yokotani, “Social Choice Correspondences with Infinitely Many Agents: Serial Dictatorship,” Social Choice and Welfare, vol. 48, pp. 573–598, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[7] Susumu Cato, “Alternative Proofs of Arrow’s General Possibility Theorem,” Economic Theory Bulletin, vol. 1, pp. 131–137, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Susumu Cato, “Weak Independence and Social Semi-Orders,” The Japanese Economic Review, vol. 66, pp. 311–321, 2015.
[Google Scholar] [Publisher Link]
[9] Maurice Queyranne, “Minimizing Symmetric Submodular Functions,” Mathematical Programming, vol. 82, pp. 3–12, 1998.
[Google Scholar] [Publisher Link]
[10] Maurice Queyrannet, “A Combinatorial Algorithm for Minimizing Symmetric Submodular Functions,” Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 98-101, 1995.
[Google Scholar] [Publisher Link]
[11] 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]
[12] Moran Feldman, “Maximizing Symmetric Submodular Functions,” ACM Transactions on Algorithms, vol. 13, no. 3, pp. 1-36, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[13] Édouard Bonnet, and Nidhi Purohit, “Metric Dimension Parameterized by Treewidth,” Algorithmica, vol. 83, no. 8, pp. 2606–2633, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Édouard Bonnet et al., “Twin-Width VI: The Lens of Contraction Sequences,” Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1036-1056, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Josse van Dobben de Bruyn, and Dion Gijswijt, “Treewidth is a Lower Bound on Graph Gonality,” Algebraic Combinatorics, vol. 3, no. 4, pp. 941–953, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[16] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos, “A Complexity Dichotomy for Hitting Connected Minors on Bounded Treewidth Graphs: The Chair and the Banner Draw the Boundary,” Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 951-970, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[17] Łukasz Bożyk et al., “On Objects Dual to Tree-Cut Decompositions,” Journal of Combinatorial Theory, Series B, vol. 157, pp. 401 428, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[18] 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]
[19] S.-il Oum and P. Seymour, “Approximating Clique-Width and Branch-Width,” Journal of Combinatorial Theory, Series B, vol. 96, no. 4, pp. 514–528, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[20] James F. Geelen, A.M.H. Gerards, and Geoff Whittle, “Branch-Width and Well-Quasi-Ordering in Matroids and Graphs,” Journal of Combinatorial Theory, Series B, vol. 84, no. 2, pp. 270–290, 2002.
[CrossRef] [Google Scholar] [Publisher Link]
[21] Fedor V. Fomin, and Dimitrios M. Thilikos, “Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up,” SIAM Journal on Computing, vol. 36, no. 2, pp. 281–309, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Susan Jowett, Jasmine Lulani Kaulamatoa, and Geoff Whittle, “Bounding Branch-Width,” The Electronic Journal of Combinatorics, pp. 1-23, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[23] Benjamin Merlin Bumpus, Kitty Meeks, and William Pettersson, “Directed Branch-Width: A Directed Analogue of Tree-Width,” arXiv preprint arXiv:2009.08903, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[24] Elena Di Lavore, and Paweł Sobociński, “Monoidal Width: Unifying Tree Width, Path Width and Branch Width,” arXiv preprint arXiv:2202.07582, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[25] Susumu Cato, “Weak Independent Decisiveness and the Existence of a Unique Vetoer,” Economics Letters, vol. 131, pp. 59–61, 2015.
[CrossRef] [Google Scholar] [Publisher Link]
[26] Lorenzo Najt, “Sampling the Vertices of a Polytope is Still Hard Even When the Branch-Width is Bounded,” 2021.
[Google Scholar] [Publisher Link]
[27] J.F. Geelen et al., “On the Excluded Minors for the Matroids of Branch-Width K,” Journal of Combinatorial Theory, Series B, vol. 88, no. 2, pp. 261–265, 2003.
[CrossRef] [Google Scholar] [Publisher Link]
[28] David Booth, “Ultrafilters on a Countable Set,” Annals of Mathematical Logic, vol. 2, no. 1, pp. 1–24, 1970.
[Google Scholar] [Publisher Link]
[29] W.W. Comfort, and S. Negrepontis, The Theory of Ultrafilters, Springer Science & Business Media, 2012.
[Google Scholar] [Publisher Link]
[30] Thomas Jech, Set Theory, Journal of Symbolic Logic, pp. 876–877, 1981.
[31] Yevhen G. Zelenyuk, Ultrafilters and Topologies on Groups, Walter de Gruyter, 2010. [Google Scholar] [Publisher Link] [32] Karel Hrbacek, and Thomas Jech, Introduction to Set Theory, Revised and Expanded, CRC Press, 1999.
[Google Scholar] [Publisher Link]
[33] John L. Bell, Set Theory: Boolean-Valued Models and Independence Proofs, OUP Oxford, vol. 47, 2011.
[Google Scholar] [Publisher Link]
[34] Pierre Samuel, “Ultrafilters and Compactification of Uniform Spaces,” Transactions of the American Mathematical Society, vol. 64, no. 1, pp. 100–132, 1948.
[Google Scholar] [Publisher Link]
[35] Kenneth Kunen, “Some Applications of Iterated Ultrapowers in Set Theory,” Annals of Mathematical Logic, vol. 1, no. 2, pp. 179–227, 1970.
[CrossRef] [Google Scholar] [Publisher Link]
[36] Simon Kochen, “Ultraproducts in the Theory of Models,” Annals of Mathematics, vol. 74, no. 2, pp. 221–261, 1961.
[CrossRef] [Google Scholar] [Publisher Link]
[37] James Cummings, “Iterated Forcing and Elementary Embeddings,” Handbook of Set Theory, pp. 775–883, 2010.
[CrossRef] [Google Scholar] [Publisher Link]
[38] Stefan Heinrich, “Ultraproducts in Banach Space Theory,” Journal for Pure and Applied Mathematics, pp. 72–104, 1980.
[CrossRef] [Google Scholar] [Publisher Link]
[39] Walter Bossert, and Kotaro Suzumura, “Quasi-Transitive and Suzumura Consistent Relations,” Social Choice and Welfare, vol. 39, pp. 323–334, 2012.
[CrossRef] [Google Scholar] [Publisher Link]
[40] Walter Bossert, and Kotaro Suzumura, “Decisive Coalitions and Coherence Properties,” Research Notebook, 2009.
[Google Scholar] [Publisher Link]

Citation :

Takaaki Fujita, "Quasi-Ultrafilter on the Connectivity System: Its Relationship to Branch-Decomposition," International Journal of Mathematics Trends and Technology (IJMTT), vol. 70, no. 3, pp. 13-16, 2024. Crossref, https://doi.org/10.14445/22315373/IJMTT-V70I3P102