Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Infinite–finite Duality Pairs of Directed Graphs

  • Published:
Order Aims and scope Submit manuscript

Abstract

The \(({\mathcal{A}},{\mathcal{D}})\) duality pairs play a crucial role in the theory of general relational structures and in Constraint Satisfaction Problems. The case where both sides are finite is fully characterized. The case where both sides 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 \({\mathcal{D}}\), and show that the elements of \({\mathcal{A}}\) must be equivalent to forests if \({\mathcal{A}}\) is an antichain. Then we construct instructive examples, where the elements of \({\mathcal{A}}\) are paths or trees. Note that the existence of infinite–finite antichain dualities was not previously known.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Duffus, D., Erdős, P.L., Nešetřil, J., Soukup, L.: Antichains in the homomorphism order of graphs. Comment Math. Univ. Carol. 48(4), 571–583 (2007)

    MATH  Google Scholar 

  2. Erdős, P.L., Soukup, L.: No finite–infinite antichain duality in the homomorphism poset of directed graphs. Order 27(3), 317–325 (2010)

    Article  MathSciNet  Google Scholar 

  3. Erdős, P.L., Tardif, C., Tardos, G.: Caterpillar dualities and regular languages. arXiv:1203.1347 (2012). Accessed 9 Nov 2012

  4. Erdős, P.L., Pálvölgyi, O., Tardif, C., Tardos, G.: On infinite–finite tree-duality pairs of relational structures. arXiv:1207.4402 (2012). Accessed 9 Nov 2012

  5. Foniok, J., Nešetřil, J., Tardif, C.: Generalized dualities and maximal finite antichains in the homomorphism order of relational structures. Eur. J. Comb. 29, 881–899 (2008)

    Article  MATH  Google Scholar 

  6. Nešetřil, J., Pultr, A.: On classes of relations and graphs determined by subobjects and factorobjects. Discrete Math. 22, 287–300 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  7. Nešetřil, J., Tardif, C.: Duality theorems for finite structures (characterising gaps and good characterisations). J. Comb. Theor. Ser. (B) 80, 80–97 (2000)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Alfréd Rényi Institute of Mathematics, Reáltanoda u 13–15, Budapest, 1053, Hungary

    Péter L. Erdős & Gábor Tardos

  2. Royal Military College of Canada, PO Box 17000, Station “Forces” Kingston, Ontario, Canada, K7K 7B4

    Claude Tardif

  3. School of Computing Science, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada, V5A 1S6

    Gábor Tardos

Authors
  1. Péter L. Erdős
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Claude Tardif
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gábor Tardos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Péter L. Erdős.

Additional information

Research of Péter L. Erdős was supported in part by the Hungarian NSF, under contracts NK 78439 and K 68262.

Research of Claude Tardif was supported by grants from NSERC and ARP.

Research of Gábor Tardos was supported in part by an NSERC Discovery grant and by the Hungarian OTKA grants T-046234, AT048826 and NK-62321.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Erdős, P.L., Tardif, C. & Tardos, G. On Infinite–finite Duality Pairs of Directed Graphs. Order 30, 807–819 (2013). https://doi.org/10.1007/s11083-012-9278-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11083-012-9278-9

Keywords

Search

Navigation