{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T07:45:35Z","timestamp":1780386335481,"version":"3.54.1"},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2012,12,7]],"date-time":"2012-12-07T00:00:00Z","timestamp":1354838400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>A perfect <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>-matching in a graph <jats:italic>G<\/jats:italic> is a spanning subgraph consisting of vertex-disjoint copies of <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>. A classic theorem of Hajnal and Szemer\u00e9di states that if <jats:italic>G<\/jats:italic> is a graph of order <jats:italic>n<\/jats:italic> with minimum degree \u03b4(<jats:italic>G<\/jats:italic>) \u2265 (<jats:italic>t<\/jats:italic> \u2212 1)<jats:italic>n<\/jats:italic>\/<jats:italic>t<\/jats:italic> and <jats:italic>t<\/jats:italic>|<jats:italic>n<\/jats:italic>, then <jats:italic>G<\/jats:italic> contains a perfect <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>-matching. Let <jats:italic>G<\/jats:italic> be a <jats:italic>t<\/jats:italic>-partite graph with vertex classes <jats:italic>V<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026, <jats:italic>V<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub> each of size <jats:italic>n<\/jats:italic>. We show that, for any \u03b3 &gt; 0, if every vertex <jats:italic>x<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> is joined to at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S096354831200048X_inline1\"\/><jats:tex-math>$\\bigl ((t-1)\/t + \\gamma \\bigr )n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices of <jats:italic>V<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub> for each <jats:italic>j<\/jats:italic> \u2260 <jats:italic>i<\/jats:italic>, then <jats:italic>G<\/jats:italic> contains a perfect <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>-matching, provided <jats:italic>n<\/jats:italic> is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.<\/jats:p>","DOI":"10.1017\/s096354831200048x","type":"journal-article","created":{"date-parts":[[2012,12,7]],"date-time":"2012-12-07T15:43:24Z","timestamp":1354895004000},"page":"97-111","source":"Crossref","is-referenced-by-count":21,"title":["A Multipartite Version of the Hajnal\u2013Szemer\u00e9di Theorem for Graphs and Hypergraphs"],"prefix":"10.1017","volume":"22","author":[{"given":"ALLAN","family":"LO","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"KLAS","family":"MARKSTR\u00d6M","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2012,12,7]]},"reference":[{"key":"S096354831200048X_ref22","unstructured":"R\u00f6dl V. , Ruci\u0144ski A. and Szemer\u00e9di E. (2009) Perfect matchings in large uniform hypergraphs with large minimum collective degree. J. Combin. Theory Ser. A 116 613\u2013636."},{"key":"S096354831200048X_ref21","doi-asserted-by":"crossref","unstructured":"Pikhurko O. (2008) Perfect matchings and K 3 4-tilings in hypergraphs of large codegree. Graphs Combin. 24 391\u2013404.","DOI":"10.1007\/s00373-008-0787-7"},{"key":"S096354831200048X_ref20","doi-asserted-by":"crossref","unstructured":"Martin R. and Szemer\u00e9di E. (2008) Quadripartite version of the Hajnal\u2013Szemer\u00e9di theorem. Discrete Math. 308 4337\u20134360.","DOI":"10.1016\/j.disc.2007.08.019"},{"key":"S096354831200048X_ref17","unstructured":"Lo A. and Markstr\u00f6m K. (2011) Perfect matchings in 3-partite 3-uniform hypergraphs. arXiv:1103.5654"},{"key":"S096354831200048X_ref16","unstructured":"Lo A. and Markstr\u00f6m K. (2011) F-factors in hypergraphs via absorption. arXiv:1105.3411"},{"key":"S096354831200048X_ref14","unstructured":"Keevash P. and Mycroft R. (2012) A multipartite Hajnal\u2013Szemer\u00e9di theorem. arXiv:1201.1882"},{"key":"S096354831200048X_ref10","unstructured":"Han J. and Zhao Y. (2012) On multipartite Hajnal\u2013Szemer\u00e9di theorems. arXiv:1203.2667"},{"key":"S096354831200048X_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/080729657"},{"key":"S096354831200048X_ref8","first-page":"601","volume-title":"Combinatorial Theory and its Applications II: Proc. Colloq., Balatonf\u00fcred, 1969","author":"Hajnal","year":"1970"},{"key":"S096354831200048X_ref6","doi-asserted-by":"crossref","unstructured":"Fischer E. (1999) Variants of the Hajnal\u2013Szemer\u00e9di theorem. J. Graph Theory 31 275\u2013282.","DOI":"10.1002\/(SICI)1097-0118(199908)31:4<275::AID-JGT2>3.0.CO;2-F"},{"key":"S096354831200048X_ref4","unstructured":"Csaba B. and Mydlarz M. (2012) Approximate multipartite version of the Hajnal\u2013Szemer\u00e9di theorem. J. Combin. Theory Ser. B 102 395\u2013410."},{"key":"S096354831200048X_ref1","doi-asserted-by":"crossref","unstructured":"Aharoni R. , Georgakopoulos A. and Spr\u00fcssel P. (2009) Perfect matchings in r-partite r-graphs. Europ. J. Combin. 30 39\u201342.","DOI":"10.1016\/j.ejc.2008.02.011"},{"key":"S096354831200048X_ref18","volume-title":"Matching Theory. Vol. 121 of North-Holland Mathematics Studies","author":"Lov\u00e1sz","year":"1986"},{"key":"S096354831200048X_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S096354831200048X_ref7","doi-asserted-by":"crossref","unstructured":"Frankl P. and R\u00f6dl V. (1985) Near perfect coverings in graphs and hypergraphs. Europ. J. Combin. 6 317\u2013326.","DOI":"10.1016\/S0195-6698(85)80045-7"},{"key":"S096354831200048X_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.02.004"},{"key":"S096354831200048X_ref11","doi-asserted-by":"crossref","unstructured":"Johansson R. (2000) Triangle-factors in a balanced blown-up triangle. Discrete Math. 211 249\u2013254.","DOI":"10.1016\/S0012-365X(99)00324-6"},{"key":"S096354831200048X_ref5","unstructured":"Daykin D. E. and H\u00e4ggkvist R. (1981) Degrees giving independent edges in a hypergraph. Bull. Austral. Math. Soc. 23 103\u2013109."},{"key":"S096354831200048X_ref19","doi-asserted-by":"crossref","unstructured":"Magyar C. and Martin R. (2002) Tripartite version of the Corr\u00e1di\u2013Hajnal theorem. Discrete Math. 254 289\u2013308.","DOI":"10.1016\/S0012-365X(01)00373-9"},{"key":"S096354831200048X_ref12","unstructured":"Keevash P. (2011) A hypergraph blow-up lemma. Random Struct. Alg. 39 275\u2013376."},{"key":"S096354831200048X_ref13","unstructured":"Keevash P. and Mycroft R. (2011) A geometric theory for hypergraph matching. arXiv:1108.1757"},{"key":"S096354831200048X_ref15","doi-asserted-by":"crossref","unstructured":"K\u00fchn D. and Osthus D. (2006) Matchings in hypergraphs of large minimum degree. J. Graph Theory 51 269\u2013280.","DOI":"10.1002\/jgt.20139"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831200048X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T20:06:05Z","timestamp":1556136365000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831200048X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,7]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S096354831200048X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831200048x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,7]]}}}