Ultrafilters and Their Dual Relationship to Tree-width in Graph Theory
Takaaki Fujita *
Independent Researcher, Shinjuku, Shinjuku-ku, Tokyo, Japan.
*Author to whom correspondence should be addressed.
Abstract
The study of width parameters in graph theory and algebraic contexts has garnered significant attention. Among these, treewidth has proven to be a pivotal parameter. The concept of "Tangle," introduced by Robertson et al., is recognized as being dual to the width parameter known as "treewidth" in graphs (Robertson & Seymour, 1991). Meanwhile, the notion of a "Filter" is well-established in the fields of topology and algebra.
In this concise paper, we propose a definition of Ultrafilters on graphs and demonstrate their equivalence to graph Tangles, thereby establishing a dual relationship with treewidth. Additionally, we explore the connection between these concepts and pathwidth.
Keywords: Filter, ultrafilter, tangle, tree-decomposition, path-decomposition, tree-width, bramble