BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jaroslav Nesetril

Jaroslav Nesetril appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.LODiscrete MathematicsLogic in Computer Sciencemath.CTmath.PRComputational Complexitymath.FA

Catalog footprint

What is connected

18works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2020arXiv

Rankwidth meets stability

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 $χ$-bounded. Our proofs are effective and lead to polynomial time algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Regular partitions of gentle graphs

Szemeredi's Regularity Lemma is a very useful tool of extremal combinatorics. Recently, several refinements of this seminal result were obtained for special, more structured classes of graphs. We survey these results in their rich combinatorial context. In particular, we stress the link to the theory of (structural) sparsity, which leads to alternative proofs, refinements and solutions of open problems. It is interesting to note that many of these classes present challenging problems. Nevertheless, from the point of view of regularity lemma type statements, they appear as "gentle" classes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cluster Analysis of Local Convergent Sequences of Structures

The cluster analysis of very large objects is an important problem, which spans several theoretical as well as applied branches of mathematics and computer science. Here we suggest a novel approach: under assumption of local convergence of a sequence of finite structures we derive an asymptotic clustering. This is achieved by a blend of analytic and geometric techniques, and particularly by a new interpretation of the authors' representation theorem for limits of local convergent sequences, which serves as a guidance for the whole process. Our study may be seen as an effort to describe connectivity structure at the limit (without having a defined explicit limit structure) and to pull this connectivity structure back to the finite structures in the sequence in a continuous way.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

First-order limits, an analytical perspective

In this paper we present a novel approach to graph (and structural) limits based on model theory and analysis. The role of Stone and Gelfand dualities is displayed prominently and leads to a general theory, which we believe is naturally emerging. This approach covers all the particular examples of structural convergence and it put the whole in new context. As an application, it leads to new intermediate examples of structural convergence and to a "grand conjecture" dealing with sparse graphs. We survey the recent developments.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Invariant measures via inverse limits of finite structures

Building on recent results regarding symmetric probabilistic constructions of countable structures, we provide a method for constructing probability measures, concentrated on certain classes of countably infinite structures, that are invariant under all permutations of the underlying set that fix all constants. These measures are constructed from inverse limits of measures on certain finite structures. We use this construction to obtain invariant probability measures concentrated on the classes of countable models of certain first-order theories, including measures that do not assign positive measure to the isomorphism class of any single model. We also characterize those transitive Borel G-spaces admitting a G-invariant probability measure, when G is an arbitrary countable product of symmetric groups on a countable set.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A note on circular chromatic number of graphs with large girth and similar problems

In this short note, we extend the result of Galluccio, Goddyn, and Hell, which states that graphs of large girth excluding a minor are nearly bipartite. We also prove a similar result for the oriented chromatic number, from which follows in particular that graphs of large girth excluding a minor have oriented chromatic number at most $5$, and for the $p$th chromatic number $χ_p$, from which follows in particular that graphs $G$ of large girth excluding a minor have $χ_p(G)\leq p+2$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Low Tree-Depth Decompositions

The theory of sparse structures usually uses tree like structures as building blocks. In the context of sparse/dense dichotomy this role is played by graphs with bounded tree depth. In this paper we survey results related to this concept and particularly explain how these graphs are used to decompose and construct more complex graphs and structures. In more technical terms we survey some of the properties and applications of low tree depth decomposition of graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Strongly polynomial sequences as interpretations

A strongly polynomial sequence of graphs $(G_n)$ is a sequence $(G_n)_{n\in\mathbb{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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Complexities of relational structures

The relational complexity, introduced by G. Cherlin, G. Martin, and D. Saracino, is a measure of ultrahomogeneity of a relational structure. It provides an information on minimal arity of additional invariant relations needed to turn given structure into an ultrahomogeneous one. The original motivation was group theory. This work focuses more on structures and provides an alternative approach. Our study is motivated by related concept of lift complexity studied by Hubicka and Nesetril.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Modeling Limits in Hereditary Classes: Reduction and Application to Trees

Limits of graphs were initiated recently in the two extreme contexts of dense and bounded degree graphs. This led to elegant limiting structures called graphons and graphings. These approach have been unified and generalized by authors in a more general setting using a combination of analytic tools and model theory to FO-limits (and X-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. These seemingly very special classes is in fact a key step in the development of limits for more general situations. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Polynomial graph invariants from homomorphism numbers

We give a method of generating strongly polynomial sequences of graphs, i.e., sequences $(H_{\mathbf{k}})$ indexed by a multivariate parameter $\mathbf{k}=(k_1,\ldots, k_h)$ such that, for each fixed graph $G$, there is a multivariate polynomial $p(G;x_1,\ldots, x_h)$ such that the number of homomorphisms from $G$ to $H_{\mathbf{k}}$ is given by the evaluation $p(G;k_1,\ldots, k_h)$. A classical example is the sequence $(K_k)$ of complete graphs, for which ${\rm hom}(G,K_k)=P(G;k)$ is the evaluation of the chromatic polynomial at $k$. Our construction produces a large family of graph polynomials that includes the Tutte polynomial, the Averbouch-Godlin-Makowsky polynomial and the Tittmann-Averbouch-Makowsky polynomial. We also introduce a new graph parameter, the {\em branching core size} of a simple graph, related to how many involutive automorphisms with fixed points it has. We prove that a countable family of graphs of bounded branching core size (which in particular implies bounded tree-depth) is always contained in a finite union of strongly polynomial sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Colouring Edges with many Colours in Cycles

The arboricity of a graph G is the minimum number of colours needed to colour the edges of G so that every cycle gets at least two colours. Given a positive integer p, we define the generalized p-arboricity Arb_p(G) of a graph G as the minimum number of colours needed to colour the edges of a multigraph G in such a way that every cycle C gets at least min(|C|; p + 1) colours. In the particular case where G has girth at least p + 1, Arb_p(G) is the minimum size of a partition of the edge set of G such that the union of any p parts induce a forest. If we require further that the edge colouring be proper, i.e., adjacent edges receive distinct colours, then the minimum number of colours needed is the generalized p-acyclic edge chromatic number of G. In this paper, we relate the generalized p-acyclic edge chromatic numbers and the generalized p-arboricities of a graph G to the density of the multigraphs having a shallow subdivision as a subgraph of G.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Interleaved adjoints on directed graphs

For an integer k >= 1, the k-th interlacing adjoint of a digraph G is the digraph i_k(G) with vertex-set V(G)^k, and arcs ((u_1, ..., u_k), (v_1, ..., v_k)) such that (u_i,v_i) \in A(G) for i = 1, ..., k and (v_i, u_{i+1}) \in A(G) for i = 1, ..., k-1. For every k we derive upper and lower bounds for the chromatic number of i_k(G) in terms of that of G. In particular, we find tight bounds on the chromatic number of interlacing adjoints of transitive tournaments. We use this result in conjunction with categorial properties of adjoint functors to derive the following consequence. For every integer ell, there exists a directed path Q_{\ell} of algebraic length ell which admits homomorphisms into every directed graph of chromatic number at least 4. We discuss a possible impact of this approach on the multifactor version of the weak Hedetniemi conjecture.

0 citations0 reviewsNo code linkedOpen access