Analytical study on Ultrafilter in Digraph: Directed Tangle and Directed Ultrafilter
Takaaki Fujita
*
Independent Researcher, Shinjuku, Shinjuku-ku, Tokyo, Japan.
*Author to whom correspondence should be addressed.
Abstract
Graph theory examines structures of vertices and edges to model relationships in diverse systems. A directed graph assigns an orientation to each edge, introducing new challenges for structural analysis. Central to this analysis is the notion of width parameters—metrics that capture a graph’s complexity via decompositions—and their dual concept, tangles, which characterize highly connected regions and are famously dual to tree-width. While both width parameters and tangles have been extensively studied in undirected graphs, their extensions to directed graphs (digraphs) have only recently attracted attention (Adler, 2007). In parallel, ultrafilters serve as a fundamental tool in topology and logic. Here, we revisit and refine the correspondence between directed tangles and ultrafilters in digraphs: we introduce the directed ultrafilter, prove its equivalence with directed tangles, and thereby improve upon the results of (Fujita, 2024f; Fujita, 2024g).
Keywords: Tangle, directed tangle, ultrafilter, directed ultrafilter, directed tree-decomposition