Search

Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomass\'e, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a~proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.

The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower ${\omega}$ levels of the MSO1 transduction hierarchy of simple graphs.

A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequence of graphs do not always admit a modeling limit, but it was conjectured that FO-convergent sequences of sufficiently sparse graphs have a modeling limits. Precisely, two conjectures were proposed: 1. If a FO-convergent sequence of graphs is residual, that is if for every integer d the maximum relative size of a ball of radius d in the graphs of the sequence tends to zero, then the sequence has a modeling limit. 2. A monotone class of graphs ${\cal C}$ has the property that every FO-convergent sequence of graphs from ${\cal C}$ has a modeling limit if and only if ${\cal C}$ is nowhere dense, that is if and only if for each integer p there is $N\left(p \right)$ such that no graph in ${\cal C}$ contains the p th subdivision of a complete graph on $N\left(p \right)$ vertices as a subgraph. In this article we prove both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense–somewhere dense dichotomy. [ABSTRACT FROM AUTHOR]

A strongly polynomial sequence of graphs ( G n ) is a sequence ( G n ) n ∈ N of finite graphs such that, for every graph F , the number of homomorphisms from F to G n is a fixed polynomial function of n (depending on F ). For example, ( K n ) is strongly polynomial since the number of homomorphisms from F to K n is the chromatic polynomial of F evaluated at n . In earlier work of de la Harpe and Jaeger, and more recently of Averbouch, Garijo, Godlin, Goodall, Makowsky, Nešetřil, Tittmann, Zilber and others, various examples of strongly polynomial sequences and constructions for families of such sequences have been found, leading to analogues of the chromatic polynomial for fractional colourings and acyclic colourings, to choose two interesting examples. We give a new model-theoretic method of constructing strongly polynomial sequences of graphs that uses interpretation schemes of graphs in more general relational structures. This surprisingly easy yet general method encompasses all previous constructions and produces many more. We conjecture that, under mild assumptions, all strongly polynomial sequences of graphs can be produced by the general method of quantifier-free interpretation of graphs in certain basic relational structures (essentially disjoint unions of transitive tournaments with added unary relations). We verify this conjecture for strongly polynomial sequences of graphs with uniformly bounded degree. [ABSTRACT FROM AUTHOR]

The colouring number col ( G ) of a graph G is the minimum integer k such that there exists a linear ordering of the vertices of G in which each vertex v has back-degree at most k , i.e. v has at most k neighbours u with u < v . The colouring number is a structural measure that measures the edge density of subgraphs of G . For r ≥ 1 , the numbers col r ( G ) and wcol r ( G ) generalise the colouring number, where col 1 ( G ) and wcol 1 ( G ) are equivalent to col ( G ) . For increasing values of r these measures converge to the well-known structural measures tree-width and tree-depth. For an n -vertex graph, col n ( G ) is equal to the tree-width of G and wcol n ( G ) is equal to the tree-depth of G . We show that if G excludes K t as a minor, then col r ( G ) ≤ ( t 2 ) ⋅ ( 2 r + 1 ) and wcol r ( G ) ≤ ( t 2 ) r ⋅ ( 2 r + 1 ) . It is easily observed that if G is planar, then col r ( G ) ≤ 5 r + 3 . The technically most demanding part of the paper is to show that for those graphs, wcol r ( G ) ≤ 5 r 5 . These results generalise to bounded genus graphs, i.e. if G is of genus g , then col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) and wcol r ( G ) ≤ 2 g ( 2 r + 1 ) + 5 r 5 . [ABSTRACT FROM AUTHOR]

We extend the general framework of structural limits from graphs and relational structures to finite structures (including function symbols). For perhaps the simplest model of this type — sets with single unary function — we determine limit objects with respect to the three main fragments of first order. In each of these cases we solve an analog of Aldous-Lyons conjecture. This builds on the experience gained when studying limits of sequences of trees. [ABSTRACT FROM AUTHOR]

Abstract: We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, . We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and homomorphism dualities. [Copyright &y& Elsevier]

Abstract: We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, . We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings and homomorphism dualities. [Copyright &y& Elsevier]