ﻻ يوجد ملخص باللغة العربية
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.
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 o
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 signatur
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 vie
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 s
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 $lambd