2020/05/08 by Michał Wrona, Wrona, Michał
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2005.04145
openalex publication_date 2020/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The relational width of a finite structure, if bounded, is always (1,1) or\n(2,3). In this paper we study the relational width of first-order expansions of\nfinitely bounded homogeneous binary cores where binary cores are structures\nwith equality and some anti-reflexive binary relations such that for any two\ndifferent elements a, b in the domain there is exactly one binary relation R\nwith (a, b) in R.\n Our main result is that first-order expansions of liberal finitely bounded\nhomogeneous binary cores with bounded strict width have relational width (2,\nMaxBound) where MaxBound is the size of the largest forbidden substructure, but\nis not less than 3, and liberal stands for structures that do not forbid\ncertain finite structures of small size. This result is built on a new approach\nand concerns a broad class of structures including reducts of homogeneous\ndigraphs for which the CSP complexity classification has not yet been obtained.\n