Maryam Mirzakhani và bài toán 4 màu tự chọn

Maryam Mirzakhani, cho tới nay, là người phụ nữ duy nhất được huy chương Fields (năm 2014). Chị sinh ra ở Iran, hai lần đoạt huy chương vàng thi toán quốc tế. Mirzakhani học đại học ở Iran, sau đó sang Mỹ, từ năm 2008 là giáo sư đại học Stanford. Chị mới qua đời mấy hôm trước, lúc mới 40 tuổi. “A light was turned off today. It breaks my heart ….. gone far too soon.” – một người bạn của chị viết trên Instagram.

Tôi chắc chắn là mình không thể hiểu được những công trình đã đem lại cho Mirzakhani huy chương Field, nhưng tôi có tìm đọc bài báo đầu tiên của chị. Bài báo có lẽ viết năm 1995 hoặc 1996, được đăng năm 1996. Bài báo liên quan đến định lý bốn màu quen thuộc. Định lý này nói rằng ta có thể dùng bốn màu (ví dụ xanh, đỏ, tím, vàng) để tô bất cứ một bản đồ nào sao cho hai nước có đường biên giới chung bao giờ cũng được tô bằng hai màu khác nhau. Định lý này được Francis Guthrie, một nhà toán học đồng thời cũng là nhà thực vật học, phát biểu năm 1852 và đã được chứng minh vào năm 1976/1977 (với sự giúp đỡ của máy tính).

Bài toán Mirzakhani xem xét cũng liên quan đến việc tô màu bản đồ. Trong bài toán 4 màu kinh điển thì 4 màu có thể coi là do một cơ quan quốc tế chọn trước, tất cả các nước phải tô theo 1 trong 4 màu đó. Ví dụ nếu cơ quan quốc tế quyết định dùng 4 màu xanh-đỏ-tím-vàng thì nước nào trên bản đồ cũng được tô bằng một trong 4 màu đó, không thể bằng màu nào khác, như màu nâu chẳng hạn.

Bây giờ ta tưởng tượng các nước không thống nhất được 4 màu dùng cho bản đồ là những màu gì. Để giải quyết sự tranh chấp, người ta cho mỗi nước được chọn 4 màu của mình. Ví dụ nước A có thể chọn xanh-đỏ-tím-vàng, nước B chọn xanh-đỏ-tím-nâu, nước C đỏ-tím-vàng-nâu v.v. Nhiệm vụ của người làm bản đồ phải tìm cách tô bản đồ sao cho

1. nước nào cũng được tô bằng 1 trong 4 màu mình chọn, và
2. không có 2 nước láng giềng nào bị tô 2 màu giống nhau.

Liệu điều này có thể làm được với tất cả các bản đồ hay không? Tức là cho một bản đồ bất kỳ, cho mỗi nước chọn 4 màu bất kỳ, có phải bao giờ cũng tồn tại một bản đổ thoả mãn hai tính chất nói trên không?

Có thể nghĩ rằng nếu các nước khác nhau chọn những bộ 4 màu khác nhau thì phải dễ tô màu bản đồ hơn là lúc tất cả các nước phải dùng 4 màu giống nhau. Giả sử ta bắt đầu tô bản đồ từ nước A, sau đó chuyển sang nước B láng giềng. Nếu bản đồ chỉ dùng bốn màu xanh-đỏ-tím-vàng, nếu ta tô nước A màu vàng, thì nước B láng giềng chỉ có thể tô bằng một trong ba màu xanh-đỏ-tím. Nhưng trong trường hợp các màu là cho các nước tự chọn, nếu bộ 4 màu của nước B là xanh-đỏ-tím-nâu thì sau khi tô nước A màu vàng ta vẫn còn đủ 4 cách tô màu nước B, thay vì 3.

Tuy nhiên, người ta đã chứng minh được là phải cho mỗi nước được chọn 5 màu thì mới chắc chắn làm được bản đồ mà không ai bị tô màu mình không muốn. Năm 1993 người ta đã tìm ra một tường hợp với 238 nước mà, với một sự chọn lựa màu của từng nước, không tồn tại bản đồ mà nước nào cũng được tô 1 trong 4 màu của mình và khác màu tất cả các nước láng giềng.

Mirzakhani tìm được một bản đồ chỉ có 63 nước và một cách chọn bộ 4 màu của từng nước mà không tồn tại cách tô màu bản đồ với những tính chất viết ở trên. Ngoài việc giảm số lượng nước từ 238 xuống 63, ví dụ của chị còn có một tính chất rất hay là về nguyên tắc, nếu các nước chấp nhận tô màu gì cũng được, thì chỉ cần 3 màu là tô được toàn bộ bản đồ. Trước đây đã có giả thuyết là nếu bản đồ có thể tô được bằng 3 màu thì cho mỗi nước tự chọn 4 màu là đủ để làm bản đồ. Ví dụ của Mirzakhani chứng tỏ giả thuyết này là sai.

Bài báo ngắn và tương đối dễ hiểu, có thể đọc ở đây. Ngoài ra có thể xem thêm bài Tuổi trẻ của một người phụ nữ đạt huy chương Fields đăng ở tạp chí Epsilon số 13, trang 299.

Dưới đây là bản đồ Mirzakhani tìm ra. Bản đồ vẽ dưới dạng graph, mối điểm là một nước, hai điểm nối với nhau bởi một đường là hai nước có chung biên giới. Điểm bên phải nối với tất cả các điểm nằm ở biên của hình bên trái. Các số ở các đỉnh tương ứng với 4 màu nước đó chọn. Muốn hiểu làm thế nào Mirzakhani tìm ra được bản đồ này thì phải đọc bài báo của chị. Không biết 63 đã phải là số nhỏ nhất chưa? Tôi đoán là chưa.