Novel Idea on Edge-Ultrafilter and Edge-Tangle

Takaaki Fujita *

Graduate School of Science and Technology, Gunma University, 1-5-1 Tenjin-Cho, Kiryu Gunma 376-8515, Japan.

*Author to whom correspondence should be addressed.


Abstract

The study of width parameters holds significant interest in both graph theory and algebraic settings. Among these, the tree-cut decomposition stands out as a key metric. The "Edge-tangle" concept is closely related to the "tree-cut width" width parameter in graph theory. This obstruction is often seen as vital for creating effective algorithms to calculate graph width, with the edge-tangle being the specific obstruction for tree-cut width. Meanwhile, the idea of an "Ultrafilter" is well-established in topology and algebra.  Due to their versatile nature, ultrafilters hold significant and broad-ranging importance. In this paper, we introduce a new concept called Edge-Ultrafilters for graphs and demonstrate how they are equivalent to Edge-tangles.

Keywords: Filter, ultrafilter, tangle, edge-tangle, tree-cut-width, tree-cut-decomposition


How to Cite

Fujita, T. (2024). Novel Idea on Edge-Ultrafilter and Edge-Tangle. Asian Research Journal of Mathematics, 20(4), 18–22. https://doi.org/10.9734/arjom/2024/v20i4794

Downloads

Download data is not yet available.

References

Liu, Chun-Hung. A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three. Journal of Combinatorial Theory, Series B. 2022;154:292-335.

Bodlaender Hans L. Treewidth: Algorithmic techniques and results. International Symposium on Mathematical Foundations of Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg; 1997.

Amini, Omid, et al. Submodular partition functions. Discrete Mathematics. 2009;309.20:6000-6008.

Diestel, Reinhard, et al. Duality and tangles of set separations. arXiv preprint arXiv:2109.08398; 2021.

Ganian, Robert, and Viktoriia Korchemna. Slim tree-cut width. arXiv preprint arXiv:2206.15091; 2022.

Ganian, Robert, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. SIAM Journal on Discrete Mathematics. 2022;36.4:2635-2666.

Giannopoulou, Archontia C, et al. Lean tree-cut decompositions: Obstructions and algorithms. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik; 2019.

Robertson, Neil, and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B. 1991;52.2:153-190.

Bienstock, Daniel, et al. Quickly excluding a forest. J. Comb. Theory, Ser. B. 1991;52.2:274-283.

Diestel, Reinhard. Ends and tangles. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. Vol. 87. No. 2. Berlin/Heidelberg: Springer Berlin Heidelberg; 2017.

Fujita, Takaaki. Reconsideration of tangle and ultrafilter using separation and partition. arXiv preprint arXiv:2305.04306; 2023.

Carnielli, Walter A, Paulo AS Veloso. Ultrafilter logic and generic reasoning. Kurt Gödel Colloquium on Computational Logic and Proof Theory. Berlin, Heidelberg: Springer Berlin Heidelberg; 1997.

Kupke, Clemens, Alexander Kurz, and Dirk Pattinson. Ultrafilter extensions for coalgebras. Algebra and Coalgebra in Computer Science: First International Conference, CALCO 2005, Swansea, UK, September 3-6, 2005. Proceedings 1. Springer Berlin Heidelberg; 2005.

Fujita, Takaaki. Proving Maximal Linear Loose Tangle as a Linear Tangle. Asian Research Journal of Mathematics. 2024;20.2:48-54.

Fujita, Takaaki. Alternative proof of linear tangle and linear obstacle: An equivalence result. Asian Research Journal of Mathematics. 2023;19.8:61-66.

Angelopoulos S, Fraignaud P, Fomin F, Nisse N, Thilikos DM. Report on GRASTA 2017, 6th Workshop on Graph Searching, Theory and Applications, Anogia, Crete, Greece. 2017;10-13. 2017.