International Journal of Mathematics Trends and Technology
Volume 70 | Issue 7 | Year 2024 | Article Id. IJMTT-V70I7P104 | DOI : https://doi.org/10.14445/22315373/IJMTT-V70I7P104
| Received | Revised | Accepted | Published |
|---|---|---|---|
| 21 May 2024 | 28 Jun 2024 | 14 Jul 2024 | 31 Jul 2024 |
The investigation of width parameters in both graph and algebraic contexts has attracted considerable
interest. Among these parameters, the linear branch width has emerged as a crucial measure. In this concise
paper, we explore the concept of linear decomposition, specifically focusing on the single filter in a connectivity
system. Additionally, we examine the relevance of matroids, antimatroids, and greedoids in the context of
connectivity systems. Our primary objective in this study is to shed light on the impediments to linear
decomposition from multiple perspectives.
Filter, Linear tangle, Tangle, Linear-decomposition, Single filter, Matroid, Antimatroid.
[1] Martin Aigner, and Michael Fromme, “A Game of Cops and Robbers,” Discrete Applied Mathematics, vol. 8, no. 1, pp. 1–12, 1984.
[CrossRef] [Publisher Link]
[2] Spyros Angelopoulos et al., “Report on Grasta 2017, 6th Workshop on Graph Searching, Theory and Applications,” CNRS, Universit ́e
Pierre et Marie Curie, 2017.
[Publisher Link]
[3] Fedor V. Fomin, and Dimitrios M. Thilikos, “An Annotated Bibliography on Guaranteed Graph Searching,” Theoretical Computer
Science, vol. 399, no. 3, pp. 236-245, 2008.
[CrossRef] [Google Scholar] [Publisher Link]
[4] Anthony Bonato, The Game of Cops and Robbers on Graphs, American Mathematical Society, 2011.
[Google Scholar]
[5] Anthony Bonato, and Boting Yang, “Graph Searching and Related Problems,” Handbook of Combinatorial Optimization, pp. 1511–
1558, 2013.
[Google Scholar]
[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] Takaaki Fujita, and Koichi Yamazaki, “Linear-width and Single Ideal,” IEICE Technical Report, vol. 117, no. 269, pp. 21-27, 2017.
[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] Neil Robertson, and Paul D. Seymour, “Graph Minors. III. Planar Tree-width,” Journal of Combinatorial Theory, Series B, vol. 36, no.
1, pp. 49-64, 1984.
[CrossRef] [Google Scholar] [Publisher Link]
[10] 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]
[11] 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]
[12] 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]
[13] Takaaki Fujita, and Koichi Yamazaki, “Equivalence Between Linear Tangle and Single Ideal,” Open Journal of Discrete Mathematics,
vol. 9, no. 1, pp. 7-10, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Dimitrios M. Thilikos, “Algorithms and Obstructions for Linear-width and Related Search Parameters,” Discrete Applied Mathematics,
vol. 105, no. 1-3, pp. 239-271, 2000.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Takaaki Fujita, and Koichi Yamazaki, “Tangle and Ultrafilter: Game Theoretical Interpretation,” Graphs and Combinatorics, vol. 36,
pp. 319-330, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[16] 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]
[17] Sandra Albrechtsen, “Refining Trees of Tangles in Abstract Separation Systems I: Inessential Parts,” arXiv, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[18] Henry H. Crapo, “Single-element Extensions of Matroids,” Journal of Research of the National Bureau of Standards Section B
Mathematics and Mathematical Physics, vol. 69B, no. 1 and 2, 1965.
[Google Scholar]
[19] Sandra R. Kingan, “Growth Rate of Binary Matroids with no P9
*
-Minor,” arXiv, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[20] William P. Miller, “Techniques in Matroid Reconstruction,” Discrete Mathematics, vol. 170, no. 1-3, pp. 173-183, 1997.
[CrossRef] [Google Scholar] [Publisher Link]
[21] Koichi Yamazaki, Tangle and Maximal Ideal, Poon, SH., Rahman, M., Yen, HC. (eds) WALCOM: Algorithms and Computation.
WALCOM 2017, Lecture Notes in Computer Science, Springer, Cham, vol 10167, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Reinhard Diestel, and Sang-il Oum, “Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract),”
International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 1-14, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[23] Walter A. Carnielli, and P.AS. Veloso, “Ultrafilter Logic and Generic Reasoning,” Computational Logic and Generic Reasoning, pp.
34-53, 1997.
[CrossRef] [Google Scholar] [Publisher Link]
[24] Tom Leinster, “Codensity and The Ultrafilter Monad,” arXiv, 2012.
[CrossRef] [Google Scholar] [Publisher Link]
[25] José G. Mijares, “A Notion of Selective Ultrafilter Corresponding to Topological Ramsey Spaces,” Mathematical Logic Quarterly, vol.
53, no. 3, pp. 255-267, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[26] Jonathan Schilhan, “Coanalytic Ultrafilter Bases,” Archive for Mathematical Logic, vol. 61, pp. 567-581, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[27] 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]
[28] 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] [Google Scholar] [Publisher Link]
[29] Reinhard Diestel et al., “Duality and Tangles of Set Separations,” Journal of Combinatorics, vol. 15, no. 1, pp. 1-39, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[30] Jean Maximilian Teegen, “Tangles, Trees of Tangles, and Submodularity,” Dissertation, Universität Hamburg, 2021.
[Google Scholar] [Publisher Link]
[31] Takaaki Fujita, “Alternative Proof of Linear Tangle and Linear Obstacle: An Equivalence Result,” Asian Research Journal of
Mathematics, vol. 19, no. 8, pp. 61-66, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[32] Takaaki Fujita, “Proving Maximal Linear Loose Tangle as a Linear Tangle,” Asian Research Journal of Mathematics, vol. 20, no. 2,
pp. 48-54, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[33] Takaaki Fujita, “Revisiting Linear Width: Rethinking the Relationship between Single Ideal and Linear Obstacle,” Journal of Advances
in Mathematics and Computer Science, vol. 38, no. 10, pp. 167–171, 2023.
[CrossRef] [Publisher Link]
[34] Frank Gurski, and Carolin Rehs, “Comparing Linear Width Parameters for Directed Graphs,” Theory of Computing Systems, vol. 63,
pp. 1358-1387, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[35] Takaaki Fujita, “Reconsideration of Tangle and Ultrafilter using Separation and Partition,” arXiv, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[36] 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. 1-4, 2006.
[Google Scholar]
[37] Atsuko Yamaguchi, Kiyoko F. Aoki, and Hiroshi Mamitsuka, “Graph Complexity of Chemical Compounds in Biological Pathways,”
Genome Informatics, vol. 14, pp. 376-377, 2003.
[CrossRef] [Google Scholar] [Publisher Link]
[38] Reinhard Diestel, “Tangles in the Social Sciences,” arXiv, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[39] Georg Gottlob, Reinhard Pichler, and Fang Wei, “Tractable Database Design and Datalog Abduction through Bounded Treewidth,”
Information Systems, vol. 35, no. 3, pp. 278-298, 2010.
[CrossRef] [Google Scholar] [Publisher Link]
[40] J. Jakes-Schauer, D. Anekstein, and P. Wocjan, “Carving-width and Contraction Trees for Tensor Networks,” arXiv, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[41] Alessandro Aloisio, and Alfredo Navarra, “Budgeted Constrained Coverage on Bounded Carving-width and Series-Parallel MultiInterface Networks,” Internet of Things, vol. 11, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[42] David R. Karger, and Nathan Srebro, Learning Markov Networks: Maximum Bounded Tree-width Graphs, SODA, 2001.
[Google Scholar] [Publisher Link]
[43] James G. Oxley, Matroid Theory, Oxford University Press, USA, 2006.
[Google Scholar]
[44] Dominic J.A. Welsh, Matroid Theory, Dover Publications, 2010.
[Google Scholar]
[45] Neil White, Matroid Applications, Cambridge University Press, 1992.
[Google Scholar]
[46] László Lovász, “Matroid Matching and Some Applications,” Journal of Combinatorial Theory, Series B, vol. 28, no. 2, pp. 208-236,
1980.
[CrossRef] [Google Scholar] [Publisher Link]
[47] František Matúš, “Matroid Representations by Partitions,” Discrete Mathematics, vol. 203, no. 1-3, pp. 169-194, 1999.
[CrossRef] [Google Scholar] [Publisher Link]
[48] Brenda L. Dietrich, “Matroids and Antimatroids-A Survey,” Discrete Mathematics, vol. 78, pp. 223-237, 1989.
[Google Scholar]
[49] Petr Hliněný et al., “Width Parameters Beyond Tree-width and Their Applications,” The Computer Journal, vol. 51, no. 3, pp. 326-362,
2008.
[CrossRef] [Google Scholar] [Publisher Link]
[50] Ephraim Korach, and Nir Solel, “Tree-width, Path-width, and Cutwidth,” Discrete Applied Mathematics, vol. 43, pp. 1, pp. 97-101,
1993.
[CrossRef] [Google Scholar] [Publisher Link]
[51] Neil Robertson, and Paul D. Seymour, “Graph Minors. II. Algorithmic Aspects of Tree-width,” Journal of Algorithms, vol. 7, no. 3, pp.
309-322, 1986.
[CrossRef] [Google Scholar] [Publisher Link]
[52] Frank Gurski, and Carolin Rehs, “Comparing Linear Width Parameters for Directed Graphs,” Theory of Computing Systems, vol. 63,
pp. 1358-1387, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[53] Takaaki Fujita, “Relation Between Ultra Matroid and Linear Decomposition,” Italian Journal of Pure and Applied Mathematics.
Accepted.
[CrossRef] [Google Scholar]
[54] Takaaki Fujita, “Quasi-Matroid on Connectivity System,” Preprint, 2023.
[Google Scholar]
[55] Yukihito Kawahara, “On Matroids and Orlik-Solomon Algebras,” Annals of Combinatorics, vol. 8, pp. 63-80, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[56] Yukito Kawahara, “Combinatorics Coming from Hyperplane Arrangements and the Orlik-Solomon Algebra (Algebraic
Combinatorics),” RIMS Kokyuroku, pp. 97-108, 2004.
[Google Scholar]
[57] Takaaki Fujita, “Novel Idea on Edge-Ultrafilter and Edge-Tangle,” Asian Research Journal of Mathematics, vol. 20, no. 4, pp. 18-22,
2024.
[CrossRef] [Google Scholar] [Publisher Link]
[58] Takaaki Fujita, “Ultrafilter in Digraph: Directed Tangle and Directed Ultrafilter,” Journal of Advances in Mathematics and Computer
Science, vol. 39, no. 3, pp. 37-42, 2024.
[CrossRef] [Google Scholar] [Publisher Link]
[59] Talal A. Al-Hawary, “Feeble-Matroids,” Italian Journal of Pure and Applied Mathematics, vol. 14, pp. 87-94, 2003.
[Google Scholar]
[60] Nadav Samet, and Boaz Tsaban, “Superfilters, Ramsey theory, and Van Der Waerden's Theorem,” Topology and its Applications, vol.
156, no. 16, pp. 2659-2669, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
Takaaki Fujita, "Matroid, Ideal, Ultrafilter, Tangle, and so on :Reconsideration of Obstruction to Linear Decomposition," International Journal of Mathematics Trends and Technology (IJMTT), vol. 70, no. 7, pp. 18-29, 2024. Crossref, https://doi.org/10.14445/22315373/IJMTT-V70I7P104
PDF 
Abstract 
Keywords 
References 
Citation