Lời giải: Chứng minh tiệm cận của Kang–Kelly–Kühn–Methuku–Osthus bằng phương pháp hấp thụ lặp (2021)

Kang, Kelly, Kühn, Methuku và Osthus (2023, Mục 1.1) khởi đầu từ ba phát biểu mà Erdős, Faber và Lovász đã đưa ra làm giả thuyết năm 1972. Phát biểu mà bài báo dùng xuyên suốt là dạng siêu đồ thị: mọi siêu đồ thị tuyến tính $\mathcal{H}$ trên $n$ đỉnh — nghĩa là $|e \cap f| \le 1$ với mọi cặp cạnh phân biệt — có chỉ số màu $\chi'(\mathcal{H}) \le n$, trong đó $\chi'(\mathcal{H})$ đếm số màu cần cho các cạnh sao cho hai cạnh cắt nhau mang màu khác nhau. Dạng thứ hai là tô màu đỉnh: nếu đồ thị $G$ là hợp của $n$ đồ thị đầy đủ, mỗi cái có nhiều nhất $n$ đỉnh và đôi một chung nhau nhiều nhất một đỉnh, thì $\chi(G) \le n$. Dạng thứ ba là phiên bản tập hợp ban đầu: cho $n$ tập hợp, mỗi tập $n$ phần tử, giao nhau đôi một nhiều nhất $1$ phần tử, ta có thể tô các phần tử bằng $n$ màu sao cho mỗi tập chứa đủ các màu khác nhau.

Tính tương đương hoàn toàn là phép đối ngẫu. Tô màu cạnh đúng của $\mathcal{H}$ chính là tô màu đỉnh đúng của đồ thị đường $L(\mathcal{H})$, trong đó mỗi đỉnh $v$ của $\mathcal{H}$ sinh ra một đồ thị đầy đủ trên các cạnh chứa $v$, và tính tuyến tính chính là điều kiện 'chung nhau nhiều nhất một đỉnh'. Ma trận liên thuộc tập hợp chuyển vị sẽ đổi chỗ hai cách đọc theo tập hợp và theo đồ thị đầy đủ. Vì vậy mọi lập luận định lượng trong chứng minh đều đặt trên $\mathcal{H}$, nơi dữ liệu bậc và đồng bậc điều khiển máy nibble.

Cận $n$ là bắt buộc, và bởi ba ví dụ khác hẳn nhau được nhắc lại ở Mục 1.1: đồ thị đầy đủ $K_n$ với $n$ lẻ, có đồ thị đường $n$-màu; cái 'bút chì gần kề' (near-pencil), một cạnh trên $n-1$ đỉnh cùng $n-1$ cạnh đi qua đỉnh còn thiếu của nó; và mặt phẳng xạ ảnh hữu hạn, khoảng $n$ cạnh đôi một cắt nhau có kích thước cỡ $\sqrt{n}$. Ba họ cực trị này sẽ tái xuất suốt chứng minh như những trường hợp không hề có khe hở.