در سال ۱۹۷۸ جف دینیتز (Jeff Dinitz) مسئله زیر را در نظریه گراف بیان کرد که به حدس دینیتز مشهور شد:
Zeilberger, D. (1996). "The Method of Undetermined Generalization and Specialization Illustrated with Fred Galvin's Amazing Proof of the Dinitz Conjecture". The American mathematical monthly. 103 (3): 233–239. arXiv:math/9506215. |access-date= requires |url= (help)
Chow, T. Y. (1995). "On the Dinitz conjecture and related conjectures". Discrete Math. 145: 145–173. Retrieved 2009-04-15.
فرض کنید L مربع از مرتبه n باشد؛ که در هر خانه (i,j) از L لیست (C(i,j از n رنگ مختلف داریم. آیا می توان به هر خانه از L یکی از رنگ های لیست آن خانه را نسبت داد به طوری که هر رنگ در هر سطر و در هر ستون حداکثر یک بار ظاهر شود؟
این مسئله در حالتی که همه لیستها برابر با {n،...۳٬۲٬۱} باشند، ساده است، کافیست ۱ تا n را در سطر اول بنویسیم، و در هر سطر دیگر اعداد سطر قبل را یک واحد چرخش دهیم تا یک مربع لاتین چرخشی به دست می آید که بوضوح شروط مسئله را ارضا می کند.
ولی مسئله همیشه به این سادگی نیست. مربعی ۲*۲ را در نظر بگیرید که
Zeilberger, D. (1996). "The Method of Undetermined Generalization and Specialization Illustrated with Fred Galvin's Amazing Proof of the Dinitz Conjecture". The American mathematical monthly. 103 (3): 233–239. arXiv:math/9506215. |access-date= requires |url= (help)
Chow, T. Y. (1995). "On the Dinitz conjecture and related conjectures". Discrete Math. 145: 145–173. Retrieved 2009-04-15.
فرض کنید L مربع از مرتبه n باشد؛ که در هر خانه (i,j) از L لیست (C(i,j از n رنگ مختلف داریم. آیا می توان به هر خانه از L یکی از رنگ های لیست آن خانه را نسبت داد به طوری که هر رنگ در هر سطر و در هر ستون حداکثر یک بار ظاهر شود؟
این مسئله در حالتی که همه لیستها برابر با {n،...۳٬۲٬۱} باشند، ساده است، کافیست ۱ تا n را در سطر اول بنویسیم، و در هر سطر دیگر اعداد سطر قبل را یک واحد چرخش دهیم تا یک مربع لاتین چرخشی به دست می آید که بوضوح شروط مسئله را ارضا می کند.
ولی مسئله همیشه به این سادگی نیست. مربعی ۲*۲ را در نظر بگیرید که
wiki: حدس دینیتز