Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-02-06T13:46:50.979Z Has data issue: false hasContentIssue false
  • English
  • Français

Towards a Weighted Version of the Hajnal–Szemerédi Theorem

Published online by Cambridge University Press:  28 February 2013

JOZSEF BALOGH ,
GRAEME KEMKES ,
CHOONGBUM LEE  and
STEPHEN J. YOUNG
JOZSEF BALOGH
Affiliation:
Department of Mathematical Sciences, University of Illinois, Urbana, IL 61801, USA (e-mail: jobal@math.uiuc.edu)
GRAEME KEMKES
Affiliation:
Department of Mathematics, Ryerson University, Toronto, ON, M5B 2K3, Canada (e-mail: gdkemkes@alumni.uwaterloo.ca)
CHOONGBUM LEE
Affiliation:
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095, USA (e-mail: choongbum.lee@gmail.com)
STEPHEN J. YOUNG
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY, 40292, UCS (e-mail: stephen.young@louisville.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

For a positive integer r ≥ 2, a Kr-factor of a graph is a collection vertex-disjoint copies of Kr which covers all the vertices of the given graph. The celebrated theorem of Hajnal and Szemerédi asserts that every graph on n vertices with minimum degree at least $(1-\frac{1}{r})n contains a Kr-factor. In this note, we propose investigating the relation between minimum degree and existence of perfect Kr-packing for edge-weighted graphs. The main question we study is the following. Suppose that a positive integer r ≥ 2 and a real t ∈ [0, 1] is given. What is the minimum weighted degree of Kn that guarantees the existence of a Kr-factor such that every factor has total edge weight at least $$t\binom{r}{2}$?$ We provide some lower and upper bounds and make a conjecture on the asymptotics of the threshold as n goes to infinity.

Keywords

Primary 05C35Secondary 05C7005C7205D40
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 3 , May 2013 , pp. 346 - 350
Copyright
Copyright © Cambridge University Press 2013

References

[1]Balogh, J., Kemkes, G., Lee, C. and Young, S. Towards a weighted version of the Hajnal–Szemerédi theorem. arXiv:1206.1376 [math.CO].Google Scholar
[2]Corrádi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14 423–439.Google Scholar
[3]Daykin, D. E. and Häggkvist, R. (1981) Degrees giving independent edges in a hypergraph. Bull. Austral. Math. Soc. 23 103–109.Google Scholar
[4]Dirac, G. A. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. (3) 269–81.CrossRefGoogle Scholar
[5]Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. In Combinatorial Theory and its Applications II: Proc. Colloq., Balatonfüred, 1969, North-Holland, pp. 601–623.Google Scholar
[6]Hàn, H., Person, Y. and Schacht, M. (2009) On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discrete Math. 23 732–748.Google Scholar