Happy triples extremal bound for l < k/2
Open problem on happy triples for $l < k/2$ · arXiv:2206.10733
Status open high confidence
The open problem asks for the best upper bound on the number of happy triples in a graph with $k$ edges and maximum degree at most $l$ in the regime $l < k/2$. Lemma 2 of arXiv:2206.10733 settles the $l \geq k/2$ case with tight extremal graphs, but the authors explicitly note that their dynamic-programming approach gives no insight into the $l < k/2$ regime. A wide web search found no follow-up work addressing this specific open problem.
Reviewer notes. No follow-up found after 5 web calls. The term 'happy triples' appears to be internal to arXiv:2206.10733 and has not been adopted in subsequent literature indexed by web search. The $l < k/2$ regime remains open as of May 2026.
Context
Lemma 2 establishes a tight bound on happy triples when $l \geq k/2$, achieved by specific extremal graphs. The authors note that their algorithmic/dynamic-programming approach gives little insight into the $l < k/2$ regime; for example, for $l=3$ and $k=3t$ the extremal graph output is $K_{t,3}$, which does not actually have maximum degree 3 for $t \geq 4$.
Notes. Stated informally in the text as 'It would be interesting to consider…'; PDF source — math may be garbled.
Source paper
Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
Patrick Hompe, Zishen Qu, Sophie Spirkl · 2023-09-11
https://arxiv.org/abs/2206.10733
PDF source