https://m2.mtmt.hu/ hun 2026-04-30 11:12 BookChapter 35203325 APPROVED true 0 false 2025-07-01T09:44:40.775+0000 2025-04-06T19:58:49.076+0000 2024-09-04T15:07:38.727+0000 true 10015168 Szakonyi Erzsebet /api/admin/10015168 Admin true 10015168 2025-04-06T19:58:49.239+0000 2025-04-06T19:58:49.239+0000 Admin 10014568 /api/admin/10014568 Vándor Andrea true 10014568 true 2025-05-12T14:54:53.914+0000 true false true 31 31 /api/publicationtype/31 PublicationType 4 true 31 BookChapter true 10000175 Abstract true 31 31 /api/publicationtype/31 PublicationType 4 true 31 BookChapter /api/subtype/10000175 Absztrakt / Kivonat SubType 453 true 10000175 true 1 /api/category/1 Category true 1 Z.L., Nagy Friendly partitions of regular graphs 40 40 2024 An internal or friendly partition of a graph is a partition of the vertices into two nonempty sets A∪B so that every vertex has at least as many neighbours in its own class as in the other one. For regular graphs, this means |N(v)∩A| ≥ deg(v)/2 for all elements v ∈ A and |N(v) ∩ B| ≥ deg(v)/2 for all elements v ∈ B. An old conjecture attributed to DeVos states that for fixed d, such a partition exists for all d-regular graphs, apart from finitely many counterexamples. This has been resolved for d ∈ {3, 4, 6}. (We remark that this is also closely related to an conjecture of Zolt´an F¨uredi, on friendly bisection of the Erd˝os-R´enyi random graph). In this talk I will give a survey of related results and highlight the following contributions, mostly related to the open d = 5 case: Theorem 0.0.8 In each n-vertex 5-regular graph, the intersection of 3-cohesive sets with minimum size contains at most n/4 + 1 vertices. Here the term k-cohesive was introduced by Ban and Linial [?] for vertex sets spanning a graph of minimum degree at least k. Note that for 5-regular graph admitting friendly partitions, the intersection of 3-cohesive sets with minimum size contains exactly zero vertices. The result relies on the combination of algebraic techniques (the Alon-Friedland-Kalai theorem, an application of the Combontorial Nullstellensatz) with combinatorial and random techniques. 40 Theorem 0.0.9 Asymptotically almost every 5-regular graph has an internal (friendly) partition. This would follow from a strengthening of the upper bound of the minimum bisection width problem for 5-regular random graphs, and refines the random process of Diaz, Serna and Wormald and their differential equation method as well. Finally we study the problem for the incidence graphs of projective planes, show several connections and applications, and point out the possible room for improvement in finding partitions where the spanning graphs of the two parts have minimum degree greater than the half of the average degree. The talk is based on a project joint work with P. Barnkopf, Z. Paulovics, E. Csóka, P. Fekete, L. Szemerédi. 2024 false true false true false NONE 2025-07-01 false 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 false 10090515 false false false 2024-12-03T16:07:44.926+0000 Gráfelmélet Osztály (HRN RAMKI); HUN-REN Rényi Alfréd Matematikai Kutatóintézet; Kombinatorika és Alkalmazásai Osztály (HRN RAMKI); Matematikai Intézet (ELTE / TTK); Synergy (HRN RAMKI); Számítógéptudományi Tanszék (ELTE / TTK / Mat_I) 4 18 6 6 0 true true 10002 English /api/language/10002 Angol Language true 2 false true 27011274 /api/publicationidentifier/27011274 https://conferences.renyi.hu/summit280/abstracts https://conferences.renyi.hu/summit280/abstracts PublicationIdentifier true 39 Full text @@@ /api/publicationsource/39 Teljes dokumentum PlainSource true true 10006 /api/publicationsourcetype/10006 PublicationSourceType true true 39 true false /api/publication/35203319 true true 32 32 /api/publicationtype/32 PublicationType 6 true 32 Book Booklet Summit280 false 35203319 false false true true false Book 2024 true 1 /api/category/1 Category true 1 false 10014568 Language 10002 /api/language/10002 Angol English true 2 true PersonAuthorship 118909884 /api/authorship/118909884 1 0.167 true false Author 10028048 /api/author/10028048 Nagy Zoltán Lóránt true 10028048 true Z.L. Nagy true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 118909885 /api/authorship/118909885 2 0.167 false false Author 10098629 /api/author/10098629 Bärnkopf Pál true true P. Barnkopf true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 118909886 /api/authorship/118909886 3 0.16666667 false false Z. Paulovics true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 118909887 /api/authorship/118909887 4 0.167 false false Author 10029947 /api/author/10029947 Csóka Endre true 10029947 true E. Csóka true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 118909888 /api/authorship/118909888 5 0.16666667 false false Author 10090515 /api/author/10090515 Fekete Panna Tímea true true P. Fekete true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 118909889 /api/authorship/118909889 6 0.16666667 false true L. Szemerédi. true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true /api/publication/35203325 <div class="BookChapter Publication long-list"> <div class="authors"> <img title="Forrásközlemény" style="float: left" src="/frontend/resources/grid/publication-core-icon.png"> <div class="autype autype0"> <span class="author-name" mtid="10028048"><a href="/gui2/?type=authors&mode=browse&sel=10028048" target="_blank">Z.L. Nagy (<span class="authorship-author-name">Nagy Zoltán Lóránt</span> <span class="authorAux-mtmt"> diszkrét matematika</span>) </a> </span> <span class="author-affil">HUN-REN Rényi Alfréd Matematikai Kutatóintézet; <span title="Eötvös Loránd Tudományegyetem">ELTE</span>/<span title="Természettudományi Kar">TTK</span>/Matematikai Intézet; <span title="Eötvös Loránd Tudományegyetem">ELTE</span>/<span title="Természettudományi Kar">TTK</span>/<span title="Matematikai Intézet">Mat_I</span>/Számítógéptudományi Tanszék</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10098629"><a href="/gui2/?type=authors&mode=browse&sel=10098629" target="_blank">P. Barnkopf (<span class="authorship-author-name">Bärnkopf Pál</span> <span class="authorAux-mtmt"> kombinatorika</span>) </a> </span> <span class="author-affil"><span title="HUN-REN Rényi Alfréd Matematikai Kutatóintézet">HRN RAMKI</span>/Gráfelmélet Osztály</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" >Z. Paulovics </span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10029947"><a href="/gui2/?type=authors&mode=browse&sel=10029947" target="_blank">E. Csóka (<span class="authorship-author-name">Csóka Endre</span> <span class="authorAux-mtmt"> matematika</span>) </a> </span> <span class="author-affil">HUN-REN Rényi Alfréd Matematikai Kutatóintézet; <span title="HUN-REN Rényi Alfréd Matematikai Kutatóintézet">HRN RAMKI</span>/Kombinatorika és Alkalmazásai Osztály</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10090515"><a href="/gui2/?type=authors&mode=browse&sel=10090515" target="_blank">P. Fekete (<span class="authorship-author-name">Fekete Panna Tímea</span> <span class="authorAux-mtmt"> Matematika</span>) </a> </span> <span class="author-affil"><span title="HUN-REN Rényi Alfréd Matematikai Kutatóintézet">HRN RAMKI</span>/Synergy</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" >L. Szemerédi. </span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;35203325" target="_blank">Friendly partitions of regular graphs</a></div> <div class="InBook"><div class="chapter-in">In:</div> <div class="authors"> </div> <div class="booktitle"><a href="/gui2/?mode=browse&params=publication;35203319" target="_blank">Booklet Summit280 </a></div> <div class="conference"> Konferencia helye, ideje: <span class="location">Budapest, Magyarország <span class="conference-date">2024.07.08. - 2024.07.12.</span> </div> : <span class="page"> p. 40. </span> <span class="year">(2024)</span> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> </span> <span class="bookchapter-ids">Befoglaló link(ek):</span> <span class="identifiers"> <span class="id identifier oa_none" title="none"> <a style="color:black" title="https://conferences.renyi.hu/summit280/abstracts" target="_blank" href="https://conferences.renyi.hu/summit280/abstracts"> Teljes dokumentum </a> </span> </span> <div class="mtid"><span class="long-pub-mtid">Közlemény: 35203325</span> | <span class="status-data status-APPROVED"> Nyilvános </span> <span class="long-book-mtid">Befoglaló: 35203319</span> Forrás | <span class="type-subtype">Egyéb konferenciaközlemény ( Absztrakt / Kivonat ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">kézi felvitel</span> </div> <div class="lastModified">Utolsó módosítás: 2025.04.06. 21:58 Szakonyi Erzsebet (RAMKI admin 4) </div> <div class="lockedBy">Központi kezelésű 2025.05.12. 16:54 Vándor Andrea (VA, admin) </div> </div> </div>