Profile complexity of K_t-minor-free graphs

Status solved high confidence

Beaudou, Bok, Foucaud, Quiroz, and Raymond (arXiv:2501.08895, 2025) prove that the r-profile complexity of $K_h$-minor-free graphs is in $O(h^{O(h)} \cdot r^{3h-3} \cdot k)$, improving Joret–Rambaud's earlier bound of $O_h(r^{h^2-1} k)$. Since the exponent $3h-3$ is $O(h)=O(t)$, this affirmatively answers Problem 42, confirming that both the profile and neighbourhood complexities of $K_t$-minor-free graphs lie in $r^{O(t)}$. The paper explicitly states it answers an open question of Joret and Rambaud.

Cited literature (1)

• proof Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs (2025)
  Laurent Beaudou, Jan Bok, Florent Foucaud, Daniel A. Quiroz, Jean-Florent Raymond · arXiv preprint · arXiv:2501.08895

  Proves the r-profile complexity of K_h-minor-free graphs is O(h^{O(h)} r^{3h-3} k), giving an exponent linear in h and thereby answering Problem 42 of Joret–Rambaud affirmatively.

Reviewer notes. The follow-up paper arXiv:2501.08895 explicitly cites Joret–Rambaud and states its main theorem answers their open question. The bound r^{3h-3} (exponent linear in h) resolves Problem 42 in the affirmative. The source paper's bound was r^{h^2-1} (quadratic exponent); the new result also improves this substantially for large h.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).