Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Ле ма про ви далення графа стверджує що якщо граф містить кілька копій даного підграфа всі його копії можна виключити ви

Лема про видалення графа

Лема про видалення графа

Ле́ма про ви́далення графа стверджує, що якщо граф містить кілька копій даного підграфа, всі його копії можна виключити видаленням малого числа ребер. Лему іноді називають ле́мою про ви́далення трику́тників у разі, коли підграф є трикутником.

Формулювання

Нехай image — граф з image вершинами. Тоді для будь-якого графа image з image вершинами, який має image ізоморфних image підграфів можна виключити всі ці підграфи, видаливши image ребер з image. Тут image означає "o мале".

Доведення та узагальнення

Лему про видалення графа спочатку довели для випадку, коли підграф є трикутником, Імре З. Ружа і Ендре Семереді (1978), використавши лему регулярності Семереді. Пізніше лему розширено на інші типи підграфів — на орієнтовані графи і гіперграфи. Альтернативне доведення, що дає сильніші межі кількості ребер, які потрібно видалити, як функцію числа копій підграфа, опублікував 2011 року Якоб Фокс.

Застосування

Ружа і Семереді сформулювали лему про видалення трикутників, щоб забезпечити підквадратичні верхні межі задачі Ружі — Семереді від розміру графів, у яких будь-яке ребро належить єдиному трикутнику. Лема про видалення графа застосовується в [en], оскільки з неї випливає, що в будь-якому графі, або граф майже вільний від графа image, або випадковими вибірками легко знайти копію image у графі. Лему про видалення гіперграфа можна використати для доведення теореми Семереді про існування довгих арифметичних прогресій у щільних підмножинах цілих чисел.

Див. також

Примітки

  1. Jacob Fox. A new proof of the graph removal lemma // Annals of Mathematics. — 2011. — Т. 174, вип. 1. — С. 561–579. — DOI:10.4007/annals.2011.174.1.17.
  2. Luca Trevisan. The Triangle Removal Lemma. — 2009. — Травень.
  3. Imre Z. Ruzsa, Endre Szemerédi. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. — North-Holland, 1978. — Т. 18. — С. 939–945.
  4. Paul Erdős, Peter Frankl, Vojtěch Rödl. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent // Graphs and Combinatorics. — 1986. — Т. 2, вип. 2. — С. 113–121. — DOI:10.1007/BF01788085.
  5. Noga Alon, Asaf Shapira. Testing subgraphs in directed graphs // Journal of Computer and System Sciences. — 2004. — Т. 69, вип. 3. — С. 353–382. — DOI:10.1016/j.jcss.2004.04.008.
  6. Terence Tao. A variant of the hypergraph removal lemma // Journal of Combinatorial Theory. — 2006. — Т. 113, вип. 7. — С. 1257–1280. — DOI:10.1016/j.jcta.2005.11.006.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Le ma pro vi dalennya grafa stverdzhuye sho yaksho graf mistit kilka kopij danogo pidgrafa vsi jogo kopiyi mozhna viklyuchiti vidalennyam malogo chisla reber Lemu inodi nazivayut le moyu pro vi dalennya triku tnikiv u razi koli pidgraf ye trikutnikom FormulyuvannyaNehaj H displaystyle H graf z h displaystyle h vershinami Todi dlya bud yakogo grafa G displaystyle G z n displaystyle n vershinami yakij maye o nh displaystyle o n h izomorfnih H displaystyle H pidgrafiv mozhna viklyuchiti vsi ci pidgrafi vidalivshi o n2 displaystyle o n 2 reber z G displaystyle G Tut o displaystyle o oznachaye o male Dovedennya ta uzagalnennyaLemu pro vidalennya grafa spochatku doveli dlya vipadku koli pidgraf ye trikutnikom Imre Z Ruzha i Endre Semeredi 1978 vikoristavshi lemu regulyarnosti Semeredi Piznishe lemu rozshireno na inshi tipi pidgrafiv na oriyentovani grafi i gipergrafi Alternativne dovedennya sho daye silnishi mezhi kilkosti reber yaki potribno vidaliti yak funkciyu chisla kopij pidgrafa opublikuvav 2011 roku Yakob Foks ZastosuvannyaRuzha i Semeredi sformulyuvali lemu pro vidalennya trikutnikiv shob zabezpechiti pidkvadratichni verhni mezhi zadachi Ruzhi Semeredi vid rozmiru grafiv u yakih bud yake rebro nalezhit yedinomu trikutniku Lema pro vidalennya grafa zastosovuyetsya v en oskilki z neyi viplivaye sho v bud yakomu grafi abo graf majzhe vilnij vid grafa H displaystyle H abo vipadkovimi vibirkami legko znajti kopiyu H displaystyle H u grafi Lemu pro vidalennya gipergrafa mozhna vikoristati dlya dovedennya teoremi Semeredi pro isnuvannya dovgih arifmetichnih progresij u shilnih pidmnozhinah cilih chisel Div takozhTeorema pro kutikiPrimitkiJacob Fox A new proof of the graph removal lemma Annals of Mathematics 2011 T 174 vip 1 S 561 579 DOI 10 4007 annals 2011 174 1 17 Luca Trevisan The Triangle Removal Lemma 2009 Traven Imre Z Ruzsa Endre Szemeredi Combinatorics Proc Fifth Hungarian Colloq Keszthely 1976 Vol II North Holland 1978 T 18 S 939 945 Paul Erdos Peter Frankl Vojtech Rodl The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent Graphs and Combinatorics 1986 T 2 vip 2 S 113 121 DOI 10 1007 BF01788085 Noga Alon Asaf Shapira Testing subgraphs in directed graphs Journal of Computer and System Sciences 2004 T 69 vip 3 S 353 382 DOI 10 1016 j jcss 2004 04 008 Terence Tao A variant of the hypergraph removal lemma Journal of Combinatorial Theory 2006 T 113 vip 7 S 1257 1280 DOI 10 1016 j jcta 2005 11 006

Дата публікації:
Топ