Обобщенная лемма о девушках
Теорема 1 (лемма о девушках). Есть n групп девушек, объединение любых k групп содержит хотя бя k различных девушек. Тогда можно в каждой группе выбрать по девушке так, чтобы выбранные девушки были различны.
(Традиционно i-ая группа есть группа девушек, симпатичных i-му юноше).
Прочитал в заметке (ftp://ftp.pdmi.ras.ru/pub/publicat/znsl/v353/p054.ps.gz) М. Звагельского про теорему Тверберга такое обобщение.
Теорема 2 (лемма о векторах). Есть n конечных групп векторов некоторого линейного пространства, объединение любых k групп содержит хотя бя k линейно независимых векторов. Тогда можно в каждой группе выбрать по вектору так, чтобы выбранные вектора были линейно независимы.
Стандартное индуктивное доказательство леммы о девушках переносится почти дословно. При индукционном переходе надо рассматривать факторпространство (в случае конечных множеств это просто теоретико-множественная разность)
В этой связи не покидает ощущение, что то и другое есть частные случаи общего утверждения о категориях с факторобъектами.
Я сам категорий не знаю, так что предлагаю подумать вам.
Спасибо flaass за ликбез, оказалась теорема Радо о матроидах. Ну конечно о матроидах!
Привет.
(Традиционно i-ая группа есть группа девушек, симпатичных i-му юноше).
Прочитал в заметке (ftp://ftp.pdmi.ras.ru/pub/publicat/znsl/v353/p054.ps.gz) М. Звагельского про теорему Тверберга такое обобщение.
Теорема 2 (лемма о векторах). Есть n конечных групп векторов некоторого линейного пространства, объединение любых k групп содержит хотя бя k линейно независимых векторов. Тогда можно в каждой группе выбрать по вектору так, чтобы выбранные вектора были линейно независимы.
Стандартное индуктивное доказательство леммы о девушках переносится почти дословно. При индукционном переходе надо рассматривать факторпространство (в случае конечных множеств это просто теоретико-множественная разность)
В этой связи не покидает ощущение, что то и другое есть частные случаи общего утверждения о категориях с факторобъектами.
Я сам категорий не знаю, так что предлагаю подумать вам.
Спасибо flaass за ликбез, оказалась теорема Радо о матроидах. Ну конечно о матроидах!
Привет.