Atserias, Albert ;
Torunczyk, Szymon
NonHomogenizable Classes of Finite Structures
Abstract
Homogenization is a powerful way of taming a class of finite structures with several interesting applications in different areas, from Ramsey theory in combinatorics to constraint satisfaction problems (CSPs) in computer science, through (finite) model theory. A few sufficient conditions for a class of finite structures to allow homogenization are known, and here we provide a necessary condition. This lets us show that certain natural classes are not homogenizable: 1) the class of locally consistent systems of linear equations over the twoelement field or any finite Abelian group, and 2) the class of finite structures that forbid homomorphisms from a specific MSOdefinable class of structures of treewidth two. In combination with known results, the first example shows that, up to ppinterpretability, the CSPs that are solvable by local consistency methods are distinguished from the rest by the fact that their classes of locally consistent instances are homogenizable. The second example shows that, for MSOdefinable classes of forbidden patterns, treewidth one versus two is the dividing line to homogenizability.
BibTeX  Entry
@InProceedings{atserias_et_al:LIPIcs:2016:6556,
author = {Albert Atserias and Szymon Torunczyk},
title = {{NonHomogenizable Classes of Finite Structures}},
booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
pages = {16:116:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770224},
ISSN = {18688969},
year = {2016},
volume = {62},
editor = {JeanMarc Talbot and Laurent Regnier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6556},
URN = {urn:nbn:de:0030drops65563},
doi = {10.4230/LIPIcs.CSL.2016.16},
annote = {Keywords: Fraiss{\'e} class, amalgmation class, reduct, Constraint Satisfaction Problem, bounded width}
}
2016
Keywords: 

Fraïssé class, amalgmation class, reduct, Constraint Satisfaction Problem, bounded width 
Seminar: 

25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Issue date: 

2016 
Date of publication: 

2016 