{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T23:20:50Z","timestamp":1776900050126,"version":"3.51.2"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:00:00Z","timestamp":1604016000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A perfect <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub>-tiling in a graph <jats:italic>G<\/jats:italic> is a collection of vertex-disjoint copies of the clique <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub> in <jats:italic>G<\/jats:italic> covering every vertex of <jats:italic>G<\/jats:italic>. The famous Hajnal\u2013Szemer\u00e9di theorem determines the minimum degree threshold for forcing a perfect <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub>-tiling in a graph <jats:italic>G<\/jats:italic>. The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph <jats:italic>G<\/jats:italic> labels from {\u20121, 1}, and one seeks substructures <jats:italic>F<\/jats:italic> of <jats:italic>G<\/jats:italic> that have \u2018high\u2019 discrepancy (<jats:italic>i.e.<\/jats:italic> the sum of the labels of the edges in <jats:italic>F<\/jats:italic> is far from 0). In this paper we determine the minimum degree threshold for a graph to contain a perfect <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub>-tiling of high discrepancy.<\/jats:p>","DOI":"10.1017\/s0963548320000516","type":"journal-article","created":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T07:19:41Z","timestamp":1604042381000},"page":"444-459","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":14,"title":["A discrepancy version of the Hajnal\u2013Szemer\u00e9di theorem"],"prefix":"10.1017","volume":"30","author":[{"given":"J\u00f3zsef","family":"Balogh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B\u00e9la","family":"Csaba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e1s","family":"Pluh\u00e1r","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Treglown","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,10,30]]},"reference":[{"key":"S0963548320000516_ref11","unstructured":"[11] Gishboliner, L. , Krivelevich, M. and Michaeli, P. (2020) Colour-biased Hamilton cycles in random graphs. arXiv:2007.12111"},{"key":"S0963548320000516_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90030-8"},{"key":"S0963548320000516_ref4","unstructured":"[4] Beck, J. and Chen, W. W. L. (1987) Irregularities of Distribution, Vol. 89 of Cambridge Tracts in Mathematics. Cambridge University Press."},{"key":"S0963548320000516_ref3","doi-asserted-by":"publisher","DOI":"10.37236\/8425"},{"key":"S0963548320000516_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2254-3"},{"key":"S0963548320000516_ref10","first-page":"47","article-title":"Discrepancy of trees","volume":"30","author":"Erd\u0151s","year":"1995","journal-title":"Stud. Sci. Math."},{"key":"S0963548320000516_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000716"},{"key":"S0963548320000516_ref6","unstructured":"[6] Catlin, P. A. (1976) Embedding subgraphs and coloring graphs under extremal degree conditions. PhD thesis, Ohio State University, Columbus."},{"key":"S0963548320000516_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2018.2"},{"key":"S0963548320000516_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00279-X"},{"key":"S0963548320000516_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.01.007"},{"key":"S0963548320000516_ref20","doi-asserted-by":"crossref","unstructured":"[20] K\u00fchn, D. and Osthus, D. (2006) Critical chromatic number and the complexity of perfect packings in graphs. In 17th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 851\u2013859. ACM.","DOI":"10.1145\/1109557.1109651"},{"key":"S0963548320000516_ref19","first-page":"295","volume-title":"Combinatorics, Paul Erd\u0151s is Eighty","volume":"2","author":"Koml\u00f3s","year":"1996"},{"key":"S0963548320000516_ref12","first-page":"601","article-title":"Proof of a conjecture of P. Erd\u0151s.","volume":"II","author":"Hajnal","year":"1970","journal-title":"Combinatorial Theory and its Applications"},{"key":"S0963548320000516_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.04.003"},{"key":"S0963548320000516_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.07.003"},{"key":"S0963548320000516_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"},{"key":"S0963548320000516_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01626028"},{"key":"S0963548320000516_ref1","first-page":"331","volume-title":"Handbook of Discrete and Computational Geometry","author":"Alexander","year":"1997"},{"key":"S0963548320000516_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/9781108332699.009"},{"key":"S0963548320000516_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0020"},{"key":"S0963548320000516_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371"},{"key":"S0963548320000516_ref13","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/0212040","article-title":"On the complexity of general graph factor problems","volume":"12","author":"Hell","year":"1983","journal-title":"SIAM J. Comput."},{"key":"S0963548320000516_ref23","first-page":"399","article-title":"Regular partitions of graphs","volume":"260","author":"Szemer\u00e9di","year":"1978","journal-title":"Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes Colloques Internationaux CNRS"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T11:59:12Z","timestamp":1618315152000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000516\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,30]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["S0963548320000516"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000516","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}