Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRankwidth meets stability
71
0
0.0
(
0
)
Added by
Sebastian Siebertz
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs $C$ is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from $C$ using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: - A class of graphs $C$ is a first-order transduction of a class with bounded treewidth if and only if $C$ has bounded rankwidth and a stable edge relation (i.e. graphs from $C$ exclude some half-graph as a semi-induced subgraph). - If a class of graphs $C$ is monadically dependent and not monadically stable, then $C$ has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly $chi$-bounded. Our proofs are effective and lead to polynomial time algorithms.
rate research
Read More
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes: 1) Graphs with linear rankwidth at most $r$ are linearly mbox{$chi$-bounded}. Actually, they have bounded $c$-chromatic number, meaning that they can be colored with $f(r)$ colors, each color inducing a cograph. 2) Based on a Ramsey-like argument, we prove for every proper hereditary family $mathcal F$ of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in~$mathcal F$. 3) For a class $mathcal C$ with bounded linear rankwidth the following conditions are equivalent: a) $mathcal C$~is~stable, b)~$mathcal C$~excludes some half-graph as a semi-induced subgraph, c) $mathcal C$ is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.
We study the (hereditary) discrepancy of definable set systems, which is a natural measure for their inherent complexity and approximability. We establish a strong connection between the hereditary discrepancy and quantifier elimination over signatures with only unary relation and function symbols. We prove that set systems definable in theories (over such signatures) with quantifier elimination have constant hereditary discrepancy. We derive that set systems definable in bounded expansion classes, which are very general classes of uniformly sparse graphs, have bounded hereditary discrepancy. We also derive that nowhere dense classes, which are more general than bounded expansion classes, in general do not admit quantifier elimination over a signature extended by an arbitrary number of unary function symbols. We show that the set systems on a ground set $U$ definable on a monotone nowhere dense class of graphs $mathscr C$ have hereditary discrepancy at most $|U|^{c}$ (for some~$c<1/2$) and that, on the contrary, for every monotone somewhere dense class $mathscr C$ and for every positive integer $d$ there is a set system of $d$-tuples definable in $mathscr C$ with discrepancy $Omega(|U|^{1/2})$. We further prove that if $mathscr C$ is a class of graphs with bounded expansion and $phi(bar x;bar y)$ is a first-order formula, then we can compute in polynomial time, for an input graph $Ginmathscr C$, a mapping $chi:V(G)^{|bar x|}rightarrow{-1,1}$ witnessing the boundedness of the discrepancy of the set-system defined by~$phi$, an $varepsilon$-net of size $mathcal{O}(1/varepsilon)$, and an $varepsilon$-approximation of size $mathcal{O}(1/varepsilon)$.
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -- a result that shows a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes. The structural results we obtain are the following. 1) The number of unlabeled graphs of order $n$ with linear rank-width at most~$r$ is at most $bigl[(r/2)!,2^{binom{r}{2}}3^{r+2}bigr]^n$. 2) Graphs with linear rankwidth at most $r$ are linearly $chi$-bounded. Actually, they have bounded $c$-chromatic number, meaning that they can be colored with $f(r)$ colors, each color inducing a cograph. 3) To the contrary, based on a Ramsey-like argument, we prove for every proper hereditary family $F$ of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in $F$. From the model theoretical side we obtain the following results: 1) A direct short proof that graphs with linear rankwidth at most $r$ are first-order transductions of linear orders. This result could also be derived from Colcombets theorem on first-order transduction of linear orders and the equivalence of linear rankwidth with linear cliquewidth. 2) For a class $C$ with bounded linear rankwidth the following conditions are equivalent: a) $C$ is stable, b) $C$ excludes some half-graph as a semi-induced subgraph, c) $C$ is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.
These are notes on discrete mathematics for computer scientists. The presentation is somewhat unconventional. Indeed I begin with a discussion of the basic rules of mathematical reasoning and of the notion of proof formalized in a natural deduction system ``a la Prawitz. The rest of the material is more or less traditional but I emphasize partial functions more than usual (after all, programs may not terminate for all input) and I provide a fairly complete account of the basic concepts of graph theory.
Affine $lambda$-terms are $lambda$-terms in which each bound variable occurs at most once and linear $lambda$-terms are $lambda$-terms in which each bound variables occurs once. and only once. In this paper we count the number of closed affine $lambda$-terms of size $n$, closed linear $lambda$-terms of size $n$, affine $beta$-normal forms of size $n$ and linear $beta$-normal forms of ise $n$, for different ways of measuring the size of $lambda$-terms. From these formulas, we show how we can derive programs for generating all the terms of size $n$ for each class. For this we use a specific data structure, which are contexts taking into account all the holes at levels of abstractions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
