{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:10:42Z","timestamp":1761621042161},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,7,16]],"date-time":"2010-07-16T00:00:00Z","timestamp":1279238400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s11083-010-9163-3","type":"journal-article","created":{"date-parts":[[2010,7,15]],"date-time":"2010-07-15T08:29:23Z","timestamp":1279182563000},"page":"327-342","source":"Crossref","is-referenced-by-count":1,"title":["Dualities and Dual Pairs in Heyting Algebras"],"prefix":"10.1007","volume":"27","author":[{"given":"Jan","family":"Foniok","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ale\u0161","family":"Pultr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claude","family":"Tardif","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,7,16]]},"reference":[{"issue":"4","key":"9163_CR1","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/BF01192520","volume":"15","author":"R Ahlswede","year":"1995","unstructured":"Ahlswede, R., Erd\u0151s, P.L., Graham, N.: A splitting property of maximal antichains. Combinatorica 15(4), 475\u2013480 (1995)","journal-title":"Combinatorica"},{"key":"9163_CR2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/978-1-4757-6048-4_4","volume-title":"Numbers, Information and Complexity, vol. 12","author":"R Ahlswede","year":"2000","unstructured":"Ahlswede, R., Khachatrian, L.H.: Splitting properties in partially ordered sets and set systems. In: Alth\u00f6fer, I., Cai, N., Dueck, G., Khachatrian, L.H., Pinsker, M.S., S\u00e1rk\u00f6zy, A., Weneger, I., Zhang, Z. (eds.) Numbers, Information and Complexity, vol. 12, pp. 29\u201344. Kluwer Academic Publishers, Boston (2000)"},{"issue":"4","key":"9163_CR3","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1016\/j.ejc.2007.11.004","volume":"29","author":"A Atserias","year":"2008","unstructured":"Atserias, A.: On digraph coloring problems and treewidth duality. Eur. J. Comb. 29(4), 796\u2013820 (2008)","journal-title":"Eur. J. Comb."},{"issue":"6","key":"9163_CR4","doi-asserted-by":"crossref","first-page":"1340","DOI":"10.4153\/CJM-1976-133-5","volume":"28","author":"B Bollob\u00e1s","year":"1976","unstructured":"Bollob\u00e1s, B., Sauer, N.: Uniquely colourable graphs with large girth. Can. J. Math. 28(6), 1340\u20131344 (1976)","journal-title":"Can. J. Math."},{"issue":"4","key":"9163_CR5","first-page":"571","volume":"48","author":"D Duffus","year":"2007","unstructured":"Duffus, D., Erd\u0151s, P.L., Ne\u0161et\u0159il, J., Soukup, L.: Antichains in the homomorphism order of graphs. Comment. Math. Univ. Carol. 48(4), 571\u2013583 (2007)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"2","key":"9163_CR6","first-page":"321","volume":"8","author":"M D\u017eamonja","year":"1992","unstructured":"D\u017eamonja, M.: A note on the splitting property in strongly dense posets of size $\\aleph_0$ . Rad. Mat. 8(2), 321\u2013326 (1992\/1998)","journal-title":"Rad. Mat."},{"key":"9163_CR7","doi-asserted-by":"crossref","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P.: Graph theory and probability. Can. J. Math. 11, 34\u201338 (1959)","journal-title":"Can. J. Math."},{"key":"9163_CR8","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF02020444","volume":"17","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hung. 17, 61\u201399 (1966)","journal-title":"Acta Math. Acad. Sci. Hung."},{"issue":"1","key":"9163_CR9","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0012-365X(96)00010-6","volume":"163","author":"PL Erd\u0151s","year":"1997","unstructured":"Erd\u0151s, P.L.: Splitting property in infinite posets. Discrete Math. 163(1), 251\u2013256 (1997)","journal-title":"Discrete Math."},{"issue":"2","key":"9163_CR10","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00493-007-0048-z","volume":"27","author":"PL Erd\u0151s","year":"2007","unstructured":"Erd\u0151s, P.L., Soukup, L.: How to split antichains in infinite posets. Combinatorica 27(2), 147\u2013161 (2007)","journal-title":"Combinatorica"},{"key":"9163_CR11","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P.L., Soukup, L.: No finite\u2013infinite antichain duality in the homomorphism poset of directed graphs. Order (2009). doi: 10.1007\/s11083-009-9118-8","DOI":"10.1007\/s11083-009-9118-8"},{"issue":"1","key":"9163_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"9163_CR13","unstructured":"Foniok, J., Ne\u0161et\u0159il, J.: Splitting finite antichains in the homomorphism order. In: Boudabbous, Y., Zaguia, N. (eds.) Proceedings of the First International Conference on Relations, Orders and Graphs: Interaction with Computer Science (ROGICS\u201908), pp. 327\u2013332 (2008)"},{"issue":"4","key":"9163_CR14","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1016\/j.ejc.2007.11.017","volume":"29","author":"J Foniok","year":"2008","unstructured":"Foniok, J., Ne\u0161et\u0159il, J., Tardif, C.: Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. Eur. J. Comb. 29(4), 881\u2013899 (2008)","journal-title":"Eur. J. Comb."},{"key":"9163_CR15","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF01886093","volume":"25","author":"D Greenwell","year":"1974","unstructured":"Greenwell, D., Lov\u00e1sz, L.: Applications of product colouring. Acta Math. Acad. Sci. Hung. 25, 335\u2013340 (1974)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9163_CR16","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0012-365X(92)90282-K","volume":"109","author":"P Hell","year":"1992","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: The core of a graph. Discrete Math. 109, 117\u2013126 (1992). Dedicated to Gert Sabidussi on the occasion of his 60th birthday","journal-title":"Discrete Math."},{"key":"9163_CR17","doi-asserted-by":"crossref","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, vol. 28. Oxford University Press (2004)","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"issue":"4","key":"9163_CR18","doi-asserted-by":"crossref","first-page":"1281","DOI":"10.1090\/S0002-9947-96-01537-1","volume":"348","author":"P Hell","year":"1996","unstructured":"Hell, P., Ne\u0161et\u0159il, J., Zhu, X.: Duality and polynomial testing of tree homomorphisms. Trans. Am. Math. Soc. 348(4), 1281\u20131297 (1996)","journal-title":"Trans. Am. Math. Soc."},{"issue":"2","key":"9163_CR19","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF02124683","volume":"9","author":"I K\u0159\u00ed\u017e","year":"1989","unstructured":"K\u0159\u00ed\u017e, I.: A hypergraph-free construction of highly chromatic graphs without short cycles. Combinatorica 9(2), 227\u2013229 (1989)","journal-title":"Combinatorica"},{"key":"9163_CR20","unstructured":"Kun, G.: Constraints, MMSNP and expander relational structures. 15 pages manuscript. arXiv:0706.1701"},{"issue":"4:6","key":"9163_CR21","first-page":"1","volume":"3","author":"B Larose","year":"2007","unstructured":"Larose, B., Loten, C., Tardif, C.: A characterisation of first-order constraint satisfaction problems. Log. Methods Comput. Sci. 3(4:6), 1\u201322 (2007)","journal-title":"Log. Methods Comput. Sci."},{"issue":"1\u20132","key":"9163_CR22","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01894680","volume":"9","author":"L Lov\u00e1sz","year":"1968","unstructured":"Lov\u00e1sz, L.: On chromatic number of finite set-systems. Acta Math. Hung. 19(1\u20132), 59\u201367 (1968)","journal-title":"Acta Math. Hung."},{"key":"9163_CR23","volume-title":"Categories for the Working Mathematician. Graduate Texts in mathematics, vol. 5","author":"S Mac Lane","year":"1998","unstructured":"Mac Lane, S.: Categories for the Working Mathematician. Graduate Texts in mathematics, vol. 5, 2nd edn. Springer, New York, Berlin, Heidelberg (1998)","edition":"2"},{"issue":"1","key":"9163_CR24","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"AK Mackworth","year":"1977","unstructured":"Mackworth, A.K.: Consistency in networks of relations. Artif. Intell. 8(1), 99\u2013118 (1977)","journal-title":"Artif. Intell."},{"key":"9163_CR25","unstructured":"Matou\u0161ek, J., Ne\u0161et\u0159il, J.: Construction of sparse graphs with given homomorphisms. Manuscript."},{"key":"9163_CR26","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Inform. Sci. 7, 95\u2013132 (1974)","journal-title":"Inform. Sci."},{"key":"9163_CR27","first-page":"385","volume-title":"Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos. on Graph Theory)","author":"V M\u00fcller","year":"1975","unstructured":"M\u00fcller, V.: On colorable critical and uniquely colorable critical graphs. In: Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos. on Graph Theory), pp. 385\u2013386. Academia, Prague (1975)"},{"issue":"2","key":"9163_CR28","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(79)90121-3","volume":"26","author":"V M\u00fcller","year":"1979","unstructured":"M\u00fcller, V.: On colorings of graphs without short cycles. Discrete Math. 26(2), 165\u2013176 (1979)","journal-title":"Discrete Math."},{"key":"9163_CR29","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/978-3-540-76796-1_13","volume-title":"Research Trends in Combinatorial Optimization","author":"J Ne\u0161et\u0159il","year":"2009","unstructured":"Ne\u0161et\u0159il, J.: Many facets of dualities. In: Cook, W.J., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 285\u2013302. Springer, Berlin, Heidelberg (2009)"},{"issue":"4","key":"9163_CR30","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1016\/j.ejc.2007.11.019","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion. III. Restricted graph homomorphism dualities. Eur. J. Comb. 29(4), 1012\u20131024 (2008)","journal-title":"Eur. J. Comb."},{"key":"9163_CR31","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits. In: A.C.M. Ran, Herman te Riele, Jan Wiegerinck (eds.) European Congress of Mathematics Amsterdam, 14\u201318 July, 2008, pp. 135\u2013165. European Mathematical Society (2010)","DOI":"10.4171\/077-1\/7"},{"issue":"3","key":"9163_CR32","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0012-365X(78)90062-6","volume":"22","author":"J Ne\u0161et\u0159il","year":"1978","unstructured":"Ne\u0161et\u0159il, J., Pultr, A.: On classes of relations and graphs determined by subobjects and factorobjects. Discrete Math. 22(3), 287\u2013300 (1978)","journal-title":"Discrete Math."},{"issue":"1","key":"9163_CR33","first-page":"9","volume":"48","author":"J Ne\u0161et\u0159il","year":"2007","unstructured":"Ne\u0161et\u0159il, J., Pultr, A., Tardif, C.: Gaps and dualities in Heyting categories. Comment. Math. Univ. Carol. 48(1), 9\u201323 (2007)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"2","key":"9163_CR34","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0095-8956(79)90084-4","volume":"27","author":"J Ne\u0161et\u0159il","year":"1979","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: A short proof of the existence of highly chromatic hypergraphs without short cycles. J. Comb. Theory, Ser. B 27(2), 225\u2013227 (1979)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"9163_CR35","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jctb.2000.1970","volume":"80","author":"J Ne\u0161et\u0159il","year":"2000","unstructured":"Ne\u0161et\u0159il, J., Tardif, C.: Duality theorems for finite structures (characterising gaps and good characterisations). J. Comb. Theory, Ser. B 80(1), 80\u201397 (2000)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"9163_CR36","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1137\/S0895480104445630","volume":"19","author":"J Ne\u0161et\u0159il","year":"2005","unstructured":"Ne\u0161et\u0159il, J., Tardif, C.: Short answers to exponentially long questions: extremal aspects of homomorphism duality. SIAM J. Discrete Math. 19(4), 914\u2013920 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"9163_CR37","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.jctb.2003.06.001","volume":"90","author":"J Ne\u0161et\u0159il","year":"2004","unstructured":"Ne\u0161et\u0159il, J., Zhu, X.: On sparse graphs with given colorings and homomorphisms. J. Comb. Theory, Ser. B 90(1), 161\u2013172 (2004)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9163_CR38","doi-asserted-by":"crossref","unstructured":"Rossman, B.: Existential positive types and preservation under homomorphisms. In: Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS\u201905), pp. 467\u2013476. IEEE Computer Society (2005)","DOI":"10.1109\/LICS.2005.16"},{"issue":"1","key":"9163_CR39","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1002\/(SICI)1097-0118(199609)23:1<33::AID-JGT3>3.0.CO;2-L","volume":"23","author":"X Zhu","year":"1996","unstructured":"Zhu, X.: Uniquely H-colorable graphs with large girth. J. Graph Theory 23(1), 33\u201341 (1996)","journal-title":"J. Graph Theory"}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-010-9163-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11083-010-9163-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-010-9163-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T05:12:13Z","timestamp":1559365933000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11083-010-9163-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,16]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9163"],"URL":"https:\/\/doi.org\/10.1007\/s11083-010-9163-3","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"value":"0167-8094","type":"print"},{"value":"1572-9273","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,16]]}}}