The colorful-complex extremal characterization conjecture

Less than 1 year old · traced to

Let GG be a graph, let U={U1,…,Um}\mathcal{U} = \{U_1, \ldots, U_m\} be a partition of V(G)V(G), and let k≥−1k \ge -1. Write Col(I(G),U)\mathbf{Col}(\mathcal{I}(G),\mathcal{U}) for the colorful complex of independent transversals, and let H~j\widetilde{H}_j denote reduced homology over a fixed ring. Suppose that

H~k(Col(I(G),U))≠0,\widetilde{H}_k(\mathbf{Col}(\mathcal{I}(G),\mathcal{U})) \neq 0,

while

H~j(Col(I(G−Ui),U−{Ui}))=0\widetilde{H}_j(\mathbf{Col}(\mathcal{I}(G-U_i),\mathcal{U}-\{U_i\})) = 0

for every Ui∈UU_i \in \mathcal{U} and every −1≤j≤k-1 \le j \le k, that GG is a disjoint union of complete bipartite graphs, and that GG has exactly ∣U∣+k|\mathcal{U}|+k connected components. The colorful-complex extremal characterization conjecture. Then for every Ui∈UU_i \in \mathcal{U}, there exists a complete bipartite component KA,BK_{A,B} of GG such that A⊆UiA \subseteq U_i.

References

Primary source

Ronen Wdowinski, “Tight constructions for reconfigurations of independent transversals”, arXiv:2604.21576 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.