Search

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 pth 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.

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as "tractable cases" of a general theory. As an outcome of this, we provide extensions of known results. We believe that this put these into next context and perspective. For example, we prove that the sparse--dense dichotomy exactly corresponds to random free graphons. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be "almost" studied component-wise. We also propose the structure of limits objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of {\em modeling} we introduce here. Our example is also the first "intermediate class" with explicitly defined limit structures., Comment: added journal reference

We consider mappings, which are structure consisting of a single function (and possibly some number of unary relations) and address the problem of approximating a continuous mapping by a finite mapping. This problem is the inverse problem of the construction of a continuous limit for first-order convergent sequences of finite mappings. We solve the approximation problem and, consequently, the full characterization of limit objects for mappings for first-order (i.e. \(\mathrm{FO}\)) convergence and local (i.e. \(\mathrm{FO}^\mathrm{local}\)) convergence. This work can be seen both as a first step in the resolution of inverse problems (like Aldous–Lyons conjecture) and a strengthening of the classical decidability result for finite satisfiability in Rabin class (which consists of first-order logic with equality, one unary function, and an arbitrary number of monadic predicates). The proof involves model theory and analytic techniques.

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion , defined as first-order transductions of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth covers (or colorings), replacing treedepth by its dense analogue called shrubdepth.

This article shows the principle of teaching the verb aspect in Polish by means of examples taken from other Slavonic languages. It presents the differences among verb aspects found in Polish, Czech, Slovak and Slovenian. The illustrative examples also document the final numer of mistakes made by foreign students whose first languages miss the right equivalent of the verb aspect. Special attention has been paid to the importance of teaching the verbal aspect in classes of language for specific purposes. W artykule podjęto problematykę nauczania aspektu czasownika na gruncie słowiańskim. Zaprezentowano różnice, dotyczące tej kategorii językowej, w językach polskim, czeskim, słowackim i słoweńskim, a następnie pokazano wynikające z tego problemy w przyswajaniu tej kategorii przez Czechów, Słowaków i Słoweńców. Szczególną uwagę zwrócono na aspekt w nauczaniu języków specjalistycznych.

International audience; We derive a framework for a posteriori error estimates in unsteady, nonlinear, possibly degenerate, advection-diffusion problems. Our estimators are based on a space-time equilibrated flux reconstruction and are locally computable. They are derived for the error measured in a space-time mesh-dependent dual norm stemming from the problem and meshes at hand augmented by a jump seminorm measuring possible nonconformities in space. Owing to this choice, a guaranteed and globally efficient upper bound is achieved, as well as robustness with respect to nonlinearities, advection dominance, domain size, final time, and absolute and relative size of space and time steps. Local-in-time and in-space efficiency is also shown for a localized upper bound of the error measure. In order to apply the framework to a given numerical method, two simple conditions, local space-time mass conservation and an approximation property of the reconstructed fluxes, need to be verified. We show how to do this for the interior-penalty discontinuous Galerkin method in space and the Crank--Nicolson scheme in time. Numerical experiments illustrate the theory.

Zykov designed one of the oldest known families of triangle-free graphs with arbitrarily high chromatic number. We determine the fractional chromatic number of the Zykov product of a family of graphs. As a corollary, we deduce that the fractional chromatic numbers of the Zykov graphs satisfy the same recurrence relation as those of the Mycielski graphs, that is a n + 1 = a n + 1 a n . This solves a conjecture of Jacobs.

An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1–3):21–33, 1994] proved that every plane graph of maximum degree Δ⩾10 can be edge-face colored with Δ + 1 colors. We extend Borodin's result to the case where Δ = 9. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:332-346, 2011 © 2011 Wiley Periodicals, Inc.

International audience; We prove that for every k and every \epsilon > 0, there exists g such that every graph with tree-width at most k and odd-girth at least g has circular chromatic number at most 2 + \epsilon.

It is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration C14. We find three configurations such that a Steiner triple system is affine if and only if it does not contain one of these configurations. Similarly, we characterise Hall triple systems using two forbidden configurations.Our characterisations have several interesting corollaries in the area of edge-colourings of graphs. A cubic graph G is S-edge-colourable for a Steiner triple system S if its edges can be coloured with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. Among others, we show that all cubic graphs are S-edge-colourable for every non-projective nonaffine point-transitive Steiner triple system S.

Reed conjectured that for every $\varepsilon>0$ and every integer $\Delta$, there exists $g$ such that the fractional total chromatic number of every graph with maximum degree $\Delta$ and girth at least $g$ is at most $\Delta+1+\varepsilon$. The conjecture was proven to be true when $\Delta=3$ or $\Delta$ is even. We settle the conjecture by proving it for the remaining cases., Comment: A typo has been corrected in the introduction (concerning the citation of the result by Ito, Kennedy and Reed)

International audience; We define nowhere dense and somewhere dense classes by means of counting of homomorphisms from test graphs. This seems to be bridging the gap between existential and counting theorems (for graph homomorphisms) and it has application to complexity of Boolean queries

A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by \emph{untangling} it, that is, by moving some of the vertices of $G$. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to untangle $\delta$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate. Our hardness results extend to a version of \textsc{1BendPointSetEmbeddability}, a well-known graph-drawing problem. Further we define fix$(G,\delta)=n-shift(G,\delta)$ to be the maximum number of vertices of a planar $n$-vertex graph $G$ that can be fixed when untangling $\delta$. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log \log n}$ vertices when untangling a drawing of an $n$-vertex graph $G$. If $G$ is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand we construct, for arbitrarily large $n$, an $n$-vertex planar graph $G$ and a drawing $\delta_G$ of $G$ with fix$(G,\delta_G) \le \sqrt{n-2}+1$ and an $n$-vertex outerplanar graph $H$ and a drawing $\delta_H$ of $H$ with fix$(H,\delta_H) \le 2 \sqrt{n-1}+1$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs., Comment: (v5) Minor, mostly linguistic changes

International audience; We prove that every n-vertex cubic bridgeless graph has at least n/2 perfect matchings and give a list of all 17 such graphs that have less than n/2+2 perfect matchings.

International audience; The measurable list chromatic number of a graph G is the smallest number such that if each vertex v of G is assigned a set L(v) of measure in a fixed atomless measure space, then there exist sets such that each c(v) has measure one and for every pair of adjacent vertices v and v'. We provide a simpler proof of a measurable generalization of Hall's theorem due to Hilton and Johnson [J Graph Theory 54 (2007), 179-193] and show that the measurable list chromatic number of a finite graph G is equal to its fractional chromatic number.

National audience; We study restricted homomorphism dualities in the context of classes with bounded expansion (which are defined by means of the greatest reduced average densities—grads). This presents a generalization of restricted dualities obtained earlier for bounded degree graphs and also for proper minor closed classes. This is related to distance coloring of graphs and to the “approximate version” of the Hadwiger conjecture.

International audience; 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, ∇r(G). For these classes we prove the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes).

Classes of graphs with bounded expansion have been introduced in [J. Nesetril, P. Ossona de Mendez, The grad of a graph and classes with bounded expansion, in: A. Raspaud, O. Delmas (Eds.), 7th International Colloquium on Graph Theory, in: Electronic Notes in Discrete Mathematics, vol. 22, Elsevier (2005), pp. 101-106; J. Nesetril, P. Ossona de Mendez, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics (2005) (submitted for publication)]. They generalize classes with forbidden topological minors (i.e. classes of graphs having no subgraph isomorphic to the subdivision of some graph in a forbidden family), and hence both proper minor closed classes and classes with bounded degree. For any class with bounded expansion C and any integer p there exists a constant N(C,p) so that the vertex set of any graph [email protected]?C may be partitioned into at most N(C,p) parts, any [email protected]?p parts of them induce a subgraph of tree-width at most (i-1) [J. Nesetril, P. Ossona de Mendez, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics (2005) (submitted for publication)] (actually, of tree-depth [J. Nesetril, P. Ossona de Mendez, Tree depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics 27 (6) (2006) 1022-1041] at most i, which is sensibly stronger). Such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities [J. Nesetril, P. Ossona de Mendez, Grad and classes with bounded expansion III. Restricted dualities, European Journal of Combinatorics (2005) (submitted for publication)]. We give here a simple algorithm for computing such partitions and prove that if we restrict the input graph to some fixed class C with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed C and p). This result is applied to get a linear time algorithm for the subgraph isomorphism problem with fixed pattern and input graphs in a fixed class with bounded expansion. More generally, let @f be a first-order logic sentence. We prove that any fixed graph property of type may be decided in linear time for input graphs in a fixed class with bounded expansion. We also show that for fixed p, computing the distances between two vertices up to distance p may be performed in constant time per query after a linear time preprocessing. Also, extending several earlier results, we show that a class of graphs has sublinear separators if it has sub-exponential expansion. This result is best possible in general.

The central problem of the total-colorings is the total-coloring conjecture, which asserts that every graph of maximum degree $\Delta$ admits a $(\Delta+2)$-total-coloring. Similar to edge-colorings—with Vizing's edge-coloring conjecture—this bound can be decreased by 1 for plane graphs of higher maximum degree. More precisely, it is known that if $\Delta\ge10$, then every plane graph of maximum degree $\Delta$ is $(\Delta+1)$-totally-colorable. On the other hand, such a statement does not hold if $\Delta\le3$. We prove that every plane graph of maximum degree 9 can be 10-totally-colored.

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 , ∇ r ( G ) . 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.

Terry Pratchett has created a fictional world, an integral part of which is a detailed and sophisticated system of place names. In his novels there are realistic names giving us an illusion of the real world and often serving as a characterization as well. Association is typical for a further kind of literary toponyms, the names refer to actual places on Earth, they activate our general cultural knowledge encyclopedia and play with the reader and his/her interpretive abilities. The last group of toponyms is purely artistic, they were created as a language game, probably the most important criterion was their aesthetic appeal. The names often deliberately destroy the illusion of reality and probability (we can talk about the anti-illusionist function), they demonstrate their artificiality, that they are a part of the author’s game. Whatever the motivation, meaning or possible allusion, all toponyms in the fictional world of the novels operate in the same way. They locate the story and help in spacial orientation within the Discworld, the names are an integral part of how the characters perceive and experience their space. Udostępnienie publikacji Wydawnictwa Uniwersytetu Łódzkiego finansowane w ramach projektu „Doskonałość naukowa kluczem do doskonałości kształcenia”. Projekt realizowany jest ze środków Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Wiedza Edukacja Rozwój; nr umowy: POWER.03.05.00-00-Z092/17-00.

We consider the colouring (or homomorphism) order C induced by all finite graphs and the existence of a homomorphism between them. This ordering may be seen as a lattice which is far from being complete. In this paper we study bounds and suprema and maximal elements in C of some frequently studied classes of graphs (such as bounded degree, degenerated and classes determined by a finite set of forbidden subgraphs). We relate these extrema to cuts of subclasses K of C (cuts are finite sets which are comparable to every element of the class K). We determine all cuts for classes of degenerated graphs. For classes of bounded degree graphs this seems to be a very difficult problem which is also mirrored by the fact that these classes fail to have a supremum. We note a striking difference between undirected and oriented graphs. This is based on the recent work of C. Tardif and J. Nešetřil. Also minor closed classes are considered and we survey recent results obtained by authors. A bit surprisingly this order setting captures Hadwiger conjecture and suggests some new problems.

The oriented chromatic number o( H ) of an oriented graph H is defined as the minimum order of an oriented graph H ′ such that H has a homomorphism to H ′. The oriented chromatic number o( G ) of an undirected graph G is then defined as the maximum oriented chromatic number of its orientations. In this paper we study the links between o( G ) and mad( G ) defined as the maximum average degree of the subgraphs of G.

List of Tables Acknowledgements Foreword S.Power Introduction: Towards a Comparison of Priority Education Policies in Europe D.Frandji Policy Interventions to Reduce Educational Inequalities: The Case of England L.Antoniou, A.Dyson & C.Raffo Priority Education Policies in Belgium: Two Modes of Regulation of the Effects of a Market Logic N.Friant, M.Demeuse, A.Aubert-Lotarski & I.Nicaise Twenty Five Years of Priority Education Policy in France: Dubious Specificity and Disappointing Results J.Rochex Greece: Educational Programmes in Support and Innovation G.Varnava-Skoura, D.Vergidis & C.Kassimi From the Invention of the Democratic City to the Management of Exclusion and Urban Violence in Portugal J.Correia, I.Cruz, J.Rochex & L.Salgado Priority Education Policies in the Czech Republic: Redesigning Equity Policies in the Post-Communist Transformation D.Greger , M.Levinska & I.Smetackova Romania: A System in Evolution, Searching for its Conceptual References C.Rus Sweden: Priority Education Policies in Times of Decentralization and Individualization G.Francia & L.Herrera Conclusion: Priority Education Policies in Europe: From One 'Age' and One Country to Another J.Rochex Bibliography Index

We relate acyclic (and star) chromatic number of a graph to the chromatic number of its minors and as a consequence we show that the set of all triangle free planar graphs is homomorphism bounded by a triangle free graph. This solves a problem posed in [[15]]. It also improves the best known bound for the star chromatic number of planar graphs from 80 to 30. Our method generalizes to all minor closed classes and puts Hadwiger conjecture in yet another context.

International audience; We exhibit a counterexample to a conjecture of Thomassen stating that the number of distinct 3-colorings of every graph whose 3-color matrix has full column rank is superpolynomial in the number of vertices.

Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A $\textit{partial permutation of length n with k holes}$ is a sequence of symbols $\pi = \pi_1 \pi_2 \cdots \pi_n$ in which each of the symbols from the set $\{1,2,\ldots,n-k\}$ appears exactly once, while the remaining $k$ symbols of $\pi$ are "holes''. We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length $k$ correspond to a Wilf-type equivalence class with respect to partial permutations with $(k-2)$ holes. Lastly, we enumerate the partial permutations of length $n$ with $k$ holes avoiding a given pattern of length at most four, for each $n \geq k \geq 1$., Nous introduisons un concept de permutations partielles. $\textit{Une permutation partielle de longueur n avec k trous}$ est une suite finie de symboles $\pi = \pi_1 \pi_2 \cdots \pi_n$ dans laquelle chaque nombre de l'ensemble $\{1,2,\ldots,n-k\}$ apparaît précisément une fois, tandis que les $k$ autres symboles de $\pi$ sont des "trous''. Nous introduisons l'étude des permutations partielles à motifs exclus et nous montrons que la plupart des résultats sur l'équivalence de Wilf peuvent être généralisés aux permutations partielles avec un nombre arbitraire de trous. De plus, nous montrons que les permutations de Baxter d'une longueur donnée $k$ forment une classe d'équivalence du type Wilf par rapport aux permutations partielles avec $(k-2)$ trous. Enfin, nous présentons l'énumération des permutations partielles de longueur $n$ avec $k$ trous qui évitent un motif de longueur $\ell \leq 4$, pour chaque $n \geq k \geq 1$.

Homomorphisms between graphs are studied as a generalization of colorings and of chromatic number. We investigate here homomorphisms from orientations of undirected planar graphs to graphs (not necessarily planar) containing as few digons as possible. We relate the existence of such homomorphisms to girth and it appears that these questions remain interesting even if we insist the girth of G is large, an assumption which makes the chromatic number easy to compute. In particular, we prove that every orientation of any large girth planar graph is Scolorable and classify those digraphs on 3, 4 and 5 vertices which color all large girth oriented planar graphs. 1. Introduction and statement of results Given graphs G = (V, E) and G’ = (V’, E’) a homomorphism from G to G’ is any mapping f : V -+ V’ satisfying LGYI E E*[f(x),f(v)l E E’. Here the brackets on both sides of the implication means the same thing: either an edge or an arc. The existence of a homomorphism from G to G’ will be denoted by G + G’. Homomorphisms are clearly related to the chromatic number of undirected graphs (an undirected graph G is k-colorable if and only if there exists a homomorphism from G to

International audience; An L(2,1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2,1)-span of a graph is the minimum possible span of its L(2,1)-labelings. We show how to compute the L(2,1)-span of a connected graph in time $O*(2.6488^n)$. Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3.2361, with 3 seemingly having been the Holy Grail.

Ce rapport est un document administratif destiné à rendre compte des actions réalisées au cours de l’année 2019 dans le cadre du Projet Collectif de Recherche consacré à la confluence Saône-Doubs à l’âge du Fer, coordonné par Emilie Dubreucq et Matthieu Thivet

We complete the Wilf classification of signed patterns of length 5 for both signed permutations and signed involutions. New general equivalences of patterns are given which prove Jaggard's conjectures concerning involutions in the symmetric group avoiding certain patterns of length 5 and 6. In this way, we also complete the Wilf classification of $S_5$, $S_6$, and $S_7$ for both permutations and involutions., Nous complétons la classification de Wilf des motifs signés de longueur 5 à la fois pour les permutations signées et les involutions signées. Nous donnons de nouvelles équivalences générales de motifs qui prouvent les conjectures de Jaggard concernant les involutions dans le groupe symétrique évitant certains motifs de longueur 5 et 6. De cette manière nous complétons également la classification de Wilf de $S_5$, $S_6$ et $S_7$ à la fois pour les permutations et les involutions.

International audience; We present results of the recent research on sparse graphs and finite structures in the context of of contemporary combinatorics, graph theory, model theory and mathematical logic, complexity of algorithms and probability theory. The topics include: complexity of subgraph- and homomorphism- problems; model checking problems for first order formulas in special classes; property testing in sparse classes of structures. All these problems can be studied under the umbrella of classes of structures which are Nowhere Dense and in the context of Nowhere Dense -- Somewhere Dense dichotomy. This dichotomy presents the classification of the general classes of structures which proves to be very robust and stable as it can be defined alternatively by most combinatorial extremal invariants as well as by algorithmic and logical terms. We give examples from logic, geometry and extremal graph theory. Finally we characterize the existence of all restricted dualities in terms of limit objects defined on the homomorphism order of graphs.