{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T05:35:30Z","timestamp":1771911330588,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1007\/s00493-013-2405-4","type":"journal-article","created":{"date-parts":[[2013,7,3]],"date-time":"2013-07-03T01:55:17Z","timestamp":1372816517000},"page":"335-347","source":"Crossref","is-referenced-by-count":14,"title":["Constraints, MMSNP and expander relational structures"],"prefix":"10.1007","volume":"33","author":[{"given":"G\u00e1bor","family":"Kun","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,7,3]]},"reference":[{"issue":"1","key":"2405_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, E. Szemer\u00e9di: Sorting in c log n parallel steps, Combinatorica 3(1), (1983), 1\u201319.","journal-title":"Combinatorica"},{"key":"2405_CR2","first-page":"454","volume-title":"17th ACM-SIAM Symposium on Discrete Algorithms","author":"N Alon","year":"2007","unstructured":"N. Alon, Oded Schwartz, Asaf Shapira: An elementary construction of constantdegree expanders, 17th ACM-SIAM Symposium on Discrete Algorithms (2007), 454\u2013458."},{"key":"2405_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33700-8_22","volume-title":"Chromatic numbers and homomorphisms of large girth hypergraphs","author":"D Duffus","year":"2006","unstructured":"D. Duffus, V. R\u00f6dl, B. Sands, N. Sauer: Chromatic numbers and homomorphisms of large girth hypergraphs, preprint, (2006)."},{"key":"2405_CR4","doi-asserted-by":"crossref","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P Erd\u0151s","year":"1959","unstructured":"P. Erd\u0151s: Graph theory and probability, Canad. J. Math. 11, (1959), 34\u201338.","journal-title":"Canad. J. Math."},{"key":"2405_CR5","first-page":"57","volume":"281","author":"T Feder","year":"1999","unstructured":"T. Feder, M. Y. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory, SIAM J. Comput. 281 (1999), 57\u2013104.","journal-title":"SIAM J. Comput."},{"key":"2405_CR6","unstructured":"S. Hoory, N. Linial, A. Widgerson: \u00c9xpander graphs and their applications, http:\/\/www.cs.huji.ac.il\/~nati\/"},{"issue":"1\u20133","key":"2405_CR7","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0012-365X(00)00245-4","volume":"233","author":"A Kostochka","year":"2001","unstructured":"A. Kostochka, J. Ne\u0161et\u0159il, P. Smol\u00edkova: Colorings and homomorphisms of bounded degree and degenerate graphs, Graph theory (Prague, 1998), Discrete Math. 233 (2001), no. 1\u20133, 257\u2013276.","journal-title":"Discrete Math."},{"key":"2405_CR8","volume-title":"On the complexity of Constraint Satisfaction Problem","author":"G Kun","year":"2006","unstructured":"G. Kun: On the complexity of Constraint Satisfaction Problem, PhD thesis (in Hungarian), 2006."},{"key":"2405_CR9","unstructured":"G. Kun, J. Ne\u0161et\u0159il: Forbidden lifts (NP and CSP for combinatorists), KAMDIMATIA Series 2006-775 (to appear in European J. Comb.)."},{"key":"2405_CR10","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01894680","volume":"19","author":"L Lov\u00e1sz","year":"1968","unstructured":"L. Lov\u00e1sz: On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar. 19 1968, 59\u201367.","journal-title":"Acta Math. Acad. Sci. Hungar."},{"issue":"3","key":"2405_CR11","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"A. Lubotzky, R. Phillips, P. Sarnak: Ramanujan graphs, Combinatorica 8(3) 261\u2013277, 1988.","journal-title":"Combinatorica"},{"key":"2405_CR12","volume-title":"Israel J. of Math.","author":"A Lubotzky","year":"2005","unstructured":"A. Lubotzky, B. Samuels, V. Vishne: Ramanujan complexes of type A d, Israel J. of Math. 2005, accepted."},{"key":"2405_CR13","volume-title":"Europ. J. of Combinatorics","author":"A Lubotzky","year":"2005","unstructured":"A. Lubotzky, B. Samuels, V. Vishne: Explicit constructions of Ramanujan complexes of type A d, Europ. J. of Combinatorics 2005, submitted."},{"key":"2405_CR14","first-page":"39","volume":"24","author":"G A Margulis","year":"1988","unstructured":"G. A. Margulis: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, J. Probl. Inf. Transm. 24, (1988), 39\u201346.","journal-title":"J. Probl. Inf. Transm."},{"key":"2405_CR15","unstructured":"J. Matou\u0161ek, J. Ne\u0161et\u0159il: Constructions of sparse graphs with given homomorphisms (to appear)."},{"key":"2405_CR16","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":"J. Ne\u0161et\u0159il, V. R\u00f6dl: A short proof of the existence of highly chromatic hypergraphs without short cycle, J. Comb. Th. B 27 (1979), 225\u2013227.","journal-title":"J. Comb. Th. B"},{"key":"2405_CR17","volume-title":"32nd Symposium on the Mathematical Foundation of Computer Science","author":"J Ne\u0161et\u0159il","year":"2007","unstructured":"J. Ne\u0161et\u0159il, M. H. Siggers: A new combinatorial approach to the Constraint Satisfaction Problem dichotomy conjecture, 32nd Symposium on the Mathematical Foundation of Computer Science, 2007, submitted."},{"issue":"1","key":"2405_CR18","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O Reingold","year":"2002","unstructured":"O. Reingold, S. Vadhan, A. Widgerson: Entropy, waves the zig-zag product, and new constant degree expanders, Annals of mathematics 155(1), (2002), 157\u2013187.","journal-title":"Annals of mathematics"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-013-2405-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-013-2405-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-013-2405-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T21:32:48Z","timestamp":1559079168000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-013-2405-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["2405"],"URL":"https:\/\/doi.org\/10.1007\/s00493-013-2405-4","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]}}}