ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Fix an integer k≥3k\geq 3. Let G=(V1,…,Vk;E)G=(V_1,\ldots,V_k;E) be a balanced kk-partite graph on knkn vertices, and let

δ^k(G)=min⁡1≤i<j≤kδ(G[Vi,Vj])\hat{\delta}_k(G)=\min_{1\leq i<j\leq k}\delta(G[V_i,V_j])

be its minimum bipartite degree. Asymptotic multipartite Hajnal–Szemerédi conjecture. If

δ^k(G)≥(k−1)n/k,\hat{\delta}_k(G)\geq (k-1)n/k,

then either GG has a perfect KkK_k-tiling, or both kk and n/kn/k are odd integers and GG is isomorphic to the fixed graph Γk(n)\Gamma_k(n). This conjecture is the multipartite analogue of the Alon–Yuster theorem on perfect graph tilings; a slightly weaker version had appeared previously. The statement identifies the minimum bipartite degree threshold and the exceptional obstruction, but the supplied text does not indicate whether the conjecture has been resolved.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.