Ризерс гипотезасы - Rysers conjecture - Wikipedia

Жылы графтар теориясы, Ризердің болжамдары - бұл сәйкес келетін максималды өлшем мен минималды көлденең өлшемге қатысты болжам гиперографтар.

Бұл болжам алғаш рет 1971 жылы Ph.D. кеңесшісі болған Дж.Р.Гендерсонның тезисі Герберт Джон Ризер.[1]

Алдын ала дайындық

A сәйкестендіру гиперграфта - бұл әр шыңның ең көбінде біреуінде пайда болатындай гипереджеттер жиынтығы. Гиперграфтағы сәйкестіктің ең үлкен мөлшері H деп белгіленеді .

A көлденең (немесе шыңның қақпағы) гиперграфта әрбір гипереджде олардың кем дегенде біреуін қамтитын шыңдар жиынтығы. Гиперграфтағы көлденең өлшемнің ең кіші мөлшері H деп белгіленеді .

Әрқайсысы үшін H, , өйткені әрбір мұқабада кез-келген сәйкестендіруде әр шетінен кем дегенде бір нүкте болуы керек.

Егер H болса р-біртекті (әр гипереджде дәл бар р шыңдар), содан кейін , өйткені кез-келген максималды сәйкестіктен жиектердің бірігуі - бұл ең көбі жиынтығы rv әр шетінен кездесетін шыңдар.

Болжам

Ризердің жорамалы, егер Н ғана емес болса р-біртекті, бірақ сонымен бірге r-партит (яғни оның шыңдарын бөлуге болады) р әрбір жиек әр жиынның бір элементінен тұратындай етіп орнатады), содан кейін:

Яғни, жоғарыдағы теңсіздіктің көбейтінді коэффициентін 1-ге азайтуға болады.[2]

Экстремалды гиперография

Ан экстремалды гиперграф Ризердің болжамына гиперграф, гиперграфия, онда гиперграфия теңдікке ие, яғни . Мұндай гипергографтардың болуы фактор екенін көрсетеді р-1 - мүмкін болатын ең кіші.

Экстремалды гиперграфтың мысалы ретінде кесілген проекциялық жазықтық - проективті жазықтық тәртіп р-1 онда бір шың және оны қамтитын барлық жолдар жойылады.[3] Ол әрқашан бар екені белгілі р-1 - жай бүтін санның қуаты.

Мұндай экстремалды гиперграфтардың басқа да отбасылары бар.[4]

Ерекше жағдайлар

Жағдайда р= 2, гиперграфия а болады екі жақты граф және болжам пайда болады . Мұның ақиқат екендігі белгілі Кёниг теоремасы.

Жағдайда р= 3, болжам дәлелдеді Рон Ахарони.[5] Дәлелі Ахарони-Гакселл теоремасы гиперграфтарда сәйкестендіруге арналған.

Жағдайларда р= 4 және р= 5, келесі әлсіз нұсқасы дәлелденді Пенни Хакселл және Скотт:[6] кейбір ε> 0 бар

.

Сонымен қатар, жағдайларда р= 4 және р= 5, Ризердің жорамалын Туза (1978) ерекше жағдайда дәлелдеді , яғни:

.

Бөлшек нұсқалар

A бөлшек сәйкестік гиперграфта әр гипергеджге салмақ қосылады, әр шыңның жанындағы салмақтың қосындысы ең көбі болады. Гиперграфтағы бөлшек сәйкестіктің ең үлкен мөлшері H деп белгіленеді .

A бөлшек көлденең гиперграфта әр гипергедждегі салмақтың қосындысы кемінде бір болатындай етіп әр шыңға салмақ тағайындау болып табылады. Гиперграфта бөлшек көлденеңнің ең кіші өлшемі H деп белгіленеді . Сызықтық бағдарламалаудың екіліктілігі оны білдіреді .

Фуреди Ризер болжамының келесі бөлшек нұсқасын дәлелдеді: Егер H болып табылады р- партиялық және р- тұрақты (әр шың дәлме-дәл пайда болады) р гипередж), содан кейін[7]

.

Ловас мұны көрсетті[8]

.

Әдебиеттер тізімі

  1. ^ Лин, Бо (2014). «Ризердің болжамына кіріспе» (PDF).
  2. ^ «Ризердің болжамдары | Ашық мәселелер бағы». www.openproblemgarden.org. Алынған 2020-07-14.
  3. ^ Туза (1983). «R-партит гиперграфтарының трансверстері бойынша Ризердің болжамы». Ars Combinatorica.
  4. ^ Әбу-Хазне, Ахмад; Барат, Янос; Покровский, Алексей; Сабо, Тибор (2018-07-12). «Ризердің болжамына арналған экстремалды гиперграфтар отбасы». arXiv:1605.06361 [математика ].
  5. ^ Ахарони, Рон (2001-01-01). «Ризердің үшжақты 3-графикалық болжам». Комбинаторика. 21 (1): 1–4. дои:10.1007 / s004930170001. ISSN  0209-9683. S2CID  13307018.
  6. ^ Хакселл, П. Скотт, А.Д. (2012-01-21). «Ризердің болжамымен». Комбинаториканың электронды журналы. 19 (1). дои:10.37236/1175. ISSN  1077-8926.
  7. ^ Фюреди, Золтан (1981-06-01). «Бірыңғай гиперграфиядағы максималды дәреже және бөлшек сәйкестіктері». Комбинаторика. 1 (2): 155–162. дои:10.1007 / bf02579271. ISSN  0209-9683. S2CID  10530732.
  8. ^ Ловас, Л. (1974), «Гиперографтарға арналған минимакс теоремалары», Гипографиялық семинар, Математика бойынша дәрістер, Берлин, Гайдельберг: Springer Berlin Heidelberg, 411, 111–126 б., дои:10.1007 / bfb0066186, ISBN  978-3-540-06846-4