Many Facets of Dualities

Jaroslav Nešetřil ()
Additional contact information
Jaroslav Nešetřil: Charles University, Department of Applied Mathematics (KAM) and Institute of Theoretical Computer Science (ITI)

Chapter 13 in Research Trends in Combinatorial Optimization, 2009, pp 285-302 from Springer

Abstract: Summary In this paper we survey results related to homomorphism dualities for graphs, and more generally, for finite structures. This is related to some of the classical combinatorial problems, such as colorings of graphs and hypergraphs, and also to recently intensively studied Constraint Satisfaction Problems. On the other side dualities are related to the descriptive complexity and First Order definability as well as to universal graphs. And in yet another context they can be expressed as properties of the homomorphism order of structures. In the contemporary context homomorphism dualities are a complex area and it is our aim to describe some of the main ideas only. However we introduce the four conceptually different proofs of the existence of duals thus indicating the versatility of this notion. Particularly we describe setting of restricted dualities and the role of bounded expansion classes.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-76796-1_13

Ordering information: This item can be ordered from
http://www.springer.com/9783540767961

DOI: 10.1007/978-3-540-76796-1_13

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().