Giả thuyết Ringel (phân rã duyên dáng)

Đã giải, 2020Tổ hợp và Toán rời rạc

Phát biểu

Với mọi số nguyên dương $n$ và mọi cây $T$ có $n$ cạnh, đồ thị đầy đủ $K_{2n+1}$ có thể được phân rã thành $2n+1$ đồ thị con đôi một rời nhau theo cạnh và đều đẳng cấu với $T$ .

Richard Montgomery, Alexey Pokrovskiy và Benny Sudakov công bố chứng minh vào tháng 1 năm 2020 (xuất bản trên Geometric and Functional Analysis năm 2021), khẳng định giả thuyết Ringel cho mọi $n$ đủ lớn. Chứng minh của họ tìm một bản sao cầu vồng của mọi cây $T$ có $n$ cạnh trong phép tô màu cạnh theo khoảng cách tự nhiên của $K_{2n+1}$ — mà $2n+1$ phép dịch chuyển vòng quanh của nó phân rã $K_{2n+1}$ — bằng cách kết hợp phép nhúng tất định cho các đỉnh bậc cao, phép nhúng ngẫu nhiên bảo toàn tính độc lập thống kê, và kỹ thuật hấp thụ phân phối. Kết quả này giải quyết giả thuyết Ringel về mặt tiệm cận mà không cần giải quyết giả thuyết cây duyên dáng Ringel–Kotzig mạnh hơn.

Giả thuyết cây duyên dáng Ringel–Kotzig — rằng mọi cây đều có phép gán nhãn đỉnh đơn ánh vào $\{0, 1, \dots, n\}$ sao cho hiệu trên các cạnh phủ đúng $\{1, 2, \dots, n\}$ — vẫn còn mở dù giả thuyết phân rã Ringel đã được giải cho $n$ lớn. Một tổng quát hóa liên quan là giả thuyết của Graham và Häggkvist rằng mọi cây $n$ cạnh đều phân rã được bất kỳ đồ thị chính quy bậc $2n$ nào.

Tài liệu tham khảo

Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov (2021). A proof of Ringel's conjecture · DOI:10.1007/s00039-021-00576-2 · arXiv:2001.02665
Alexander Rosa (1967). On certain valuations of the vertices of a graph

Lịch sử bài toán

1963Gerhard Ringel đặt ra giả thuyết tại hội nghị lý thuyết đồ thị ở Smolenice, hỏi liệu $K_{2n+1}$ có luôn phân rã được thành $2n+1$ bản sao của một cây bất kỳ có $n$ cạnh hay không.
1967Alexander Rosa đưa ra khái niệm $\beta$ -định giá (sau này được Solomon Golomb gọi là phép gán nhãn duyên dáng) và chứng minh rằng nếu cây $T$ có $n$ cạnh có gán nhãn duyên dáng thì $K_{2n+1}$ phân rã vòng quanh thành $2n+1$ bản sao của $T$ .
2016Joos, Kim, Kühn và Osthus chứng minh giả thuyết Ringel cho mọi cây bậc bị chặn đủ lớn nhờ bổ đề thổi phồng cho các phân rã.
2020Montgomery, Pokrovskiy và Sudakov chứng minh giả thuyết Ringel (cùng giả thuyết phân rã vòng quanh của Kotzig) cho mọi cây đủ lớn với bậc cực đại tùy ý.