Prechains and self duality

详细信息	查看全文 | 推荐本文 |

• 作者：Youssef Boudabbous^a ; ¹ ; ^{yboudabbous@ksu.edu.sa} ; Christian Delhommé ; ^b ; ^{delhomme@univ-reunion.fr}
• 关键词：Self dual binary relation ; Circular orderings ; Graph decomposition
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 May, 2012
• 卷：312
• 期：10
• 页码：1743-1765
• 文件大小：447 K

摘要

We call prechain any binary relation for which the circular closure of the ternary relation is a circular ordering, where means 聽; i.e.聽 is a prechain if and only if聽there exists a linear strict ordering on such that for any , and in , ( or or ) is equivalent to ( or or ). Thus a chain , i.e.聽a set endowed with a linear strict ordering , is trivially a prechain. We characterize the class of prechains by a finite list of finite forbidden induced subrelations, and we give a description of those prechains. As an application, we obtain, for each integer , a description of the (possibly infinite) -self dual binary relations. A binary relation is said to be -self dual if each relation induced on at most vertices is isomorphic to the relation obtained by reversing its arcs. That extends results previously known in the finite case, of which the proofs were obtained as byproducts of the description of difference classes w.r.t.聽-hypomorphy in reconstruction.