Various Properties of Various Ultrafilters, Various Graph Width Parameters, and Various Connectivity Systems (with Survey)
For researchers in graph theory and computational complexity, this work offers a novel perspective and potential tools for unifying width parameters, but it is primarily a theoretical and survey contribution without concrete performance numbers.
This book introduces ultrafilters on connectivity systems and explores their connections to graph width parameters, providing a unified framework for studying graph complexity. It develops new results on ultrafilters and related notions, and surveys a wide range of graph width parameters to stimulate further research.
This book studies ultrafilters on connectivity systems, that is, on pairs \((X,f)\) where \(X\) is a finite set and \(f:2^{X}\to \mathbb{N}\) is a symmetric submodular function. Ultrafilters, which play a fundamental role in topology and set theory, are considered here in this broader setting, with particular emphasis on their connections to graph width parameters and to the structural analysis of graph complexity. We develop several results on ultrafilters on connectivity systems and examine related notions such as prefilters, ultra-prefilters, and filter subbases. We also discuss additional width-, length-, and depth-type parameters that naturally arise in this framework, thereby broadening the perspective from which graph structure may be studied. In addition, the book compares a wide range of graph width parameters and related concepts, with the aim of providing a unified viewpoint and a useful point of departure for further research in graph theory and computational complexity. More broadly, the book highlights connections with several neighboring areas of mathematics, including set theory, lattice theory, and matroid theory. It also contains survey-style material intended to clarify the current landscape of graph width theory and to stimulate further developments in the subject.