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

Claude Tardif

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

ResearcherUnclaimed source record
math.COmath.CTDiscrete MathematicsLogic in Computer ScienceComputational Complexity

Catalog footprint

What is connected

13works
5topics
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

13 published item(s)

preprint2016arXiv

Generalised Mycielski graphs and bounds on chromatic numbers

We prove that the coindex of the box complex $\mathrm{B}(H)$ of a graph $H$ can be measured by the generalised Mycielski graphs which admit a homomorphism to it. As a consequence, we exhibit for every graph $H$ a system of linear equations solvable in polynomial time, with the following properties: If the system has no solutions, then $\mathrm{coind}(\mathrm{B}(H)) + 2 \leq 3$; if the system has solutions, then $χ(H) \geq 4$. We generalise the method to other bounds on chromatic numbers using linear algebra.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Topologically $4$-chromatic graphs and signatures of odd cycles

We investigate group-theoretic "signatures" of odd cycles of a graph, and their connections to topological obstructions to 3-colourability. In the case of signatures derived from free groups, we prove that the existence of an odd cycle with trivial signature is equivalent to having the coindex of the hom-complex at least 2 (which implies that the chromatic number is at least 4). In the case of signatures derived from elementary abelian 2-groups we prove that the existence of an odd cycle with trivial signature is a sufficient condition for having the index of the hom-complex at least 2 (which again implies that the chromatic number is at least 4).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Homomorphisms of binary Cayley graphs

A binary Cayley graph is a Cayley graph based on a binary group. In 1982, Payan proved that any non-bipartite binary Cayley graph must contain a generalized Mycielski graph of an odd-cycle, implying that such a graph cannot have chromatic number 3. We strengthen this result first by proving that any non-bipartite binary Cayley graph must contain a projective cube as a subgraph. We further conjecture that any homo- morphism of a non-bipartite binary Cayley graph to a projective cube must be surjective and we prove some special case of this conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Regular families of forests, antichains and duality pairs of relational structures

Homomorphism duality pairs play crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper we characterize the infinite-finite antichain dualities and infinite-finite dualities with trees or forest on the left hand side. This work builds on our earlier papers that gave several examples of infinite-finite antichain duality pairs of directed graphs and a complete characterization for caterpillar dualities.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Digraph functors which admit both left and right adjoints

For our purposes, two functors Λ and Γ are said to be respectively left and right adjoints of each other if for any digraphs G and H, there exists a homomorphism of Λ(G) to H if and only if there exists a homomorphism of G to Γ(H). We investigate the right adjoints characterised by Pultr in [A. Pultr, The right adjoints into the categories of relational systems, in Reports of the Midwest Category Seminar, IV, volume 137 of Lecture Notes in Mathematics, pages 100-113, Berlin, 1970]. We find necessary conditions for these functors to admit right adjoints themselves. We give many examples where these necessary conditions are satisfied, and the right adjoint indeed exists. Finally, we discuss a connection between these right adjoints and homomorphism dualities.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On infinite-finite duality pairs of directed graphs

The (A,D) duality pairs play crucial role in the theory of general relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper (which is the first one of a series) we start the detailed study of the infinite-finite case. Here we concentrate on directed graphs. We prove some elementary properties of the infinite-finite duality pairs, including lower and upper bounds on the size of D, and show that the elements of A must be equivalent to forests if A is an antichain. Then we construct instructive examples, where the elements of A are paths or trees. Note that the existence of infinite-finite antichain dualities was not previously known.

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
preprint2009arXiv

Adjoint functors and tree duality

A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existence of a homomorphism from any member of T to G. A digraph H is said to have tree duality if there exists a complete set of obstructions T consisting of orientations of trees. We show that if H has tree duality, then its arc graph delta H also has tree duality, and we derive a family of tree obstructions for delta H from the obstructions for H. Furthermore we generalise our result to right adjoint functors on categories of relational structures. We show that these functors always preserve tree duality, as well as polynomial CSPs and the existence of near-unanimity functions.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

A Characterisation of First-Order Constraint Satisfaction Problems

We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores. A slight modification of this algorithm provides, for first-order definable CSP's, a simple poly-time algorithm to produce a solution when one exists. As an application of our algebraic characterisation of first order CSP's, we describe a large family of L-complete CSP's.

0 citations0 reviewsNo code linkedOpen access