KOMBINATORIKA SZEMINÁRIUM
2024/2025
ARCHÍVUM ELŐKÉSZÜLETBEN
2025. április 25. (10:30)
Riesz terem
Simonyi Gábor
Rényi Intézet, BME

Érdekességek Schrijver gráfokról

Az $SG(n,k)$ Schrijver gráf csúcsait az $[n]={1,2,...,n}$ halmaz azon $k$ elemű részhalmazai alkotják, melyek nem tartalmaznak ciklikusan szomszédos elemeket, azaz olyanokat, amikben $i$ és $i+1$ vagy $n$ és $1$ egyszerre előfordul. Két ilyen csúcs akkor van összekötve, ha a megfelelő halmazok diszjunktak.

Ez a gráf feszített részgráfja a $KG(n,k)$ Kneser gráfnak, ami az $[n]$ halmaz összes $k$ elemű részhalmazán van hasonlóan definiálva és amiről Lovász híres eredménye, hogy a kromatikus száma pontosan $n-2k+2$.

Schrijver Lovász topologikus módszerét használva észrevette, hogy még $SG(n,k)$ kromatikus száma is ugyanennyi, de annak bármely csúcsát elhagyva ez már nem igaz, vagyis $SG(n,k)$ csúcs-színkritikus.

Az előadásban további kritikussági tulajdonságokról lesz szó, például, hogy mely élei lehetnek színkritikusak $SG(n,k)$-nak, illetve, hogy $SG(n,k)$ milyen feszített részgráfja (csúcs)kritikus a tört kromatikus számra nézve, amely paraméter szintén azonos értéket vesz fel a $KG(n,k)$ és az $SG(n,k)$ gráfokon.

Az eredmények egyik része Tardos Gáborral, másik része Gujgiczer Annával közös.

2025. április 11. (10:40)
Riesz terem
Borbényi Márton
ELTE & Rényi Intézet

Statisztikus fizikai modellek nagybőségű gráfokon

Az Ising-modell a statisztikus mechanika egyik alapvető modellje, amely a mágnesek működésére ad egy magyarázatot. Egyszerű definíciója ellenére viselkedése komplex, különösen a kritikus pont közelében, ahol a hőmérséklet apró változtatása is drámai változásokat idézhet elő a rendszer makroszkopikus tulajdonságaiban, mint például a mágnesezettségben.

Előadásomban beszélni fogunk erről, és más hasonló statisztikus fizikai modellről, mint például a Potts- és a véletlen klaszter modell. Végül pedig lesz szó ezen modellek kapcsolatáról nagybőségű gráfokon, amit Bencs Ferenccel és Csikvári Péterrel közösen bizonyítottunk.

2025. március 21. (10:15)
Riesz terem
Jung Attila
Rényi Intézet

A kvantitatív frakcionális Helly tétel

Helly tételének két nevezetes kiterjesztése Katchalski és Liu (1979) frakcionális Helly tétele, valamint Bárány, Katchalski és Pach (1982) kvantitatív Helly tétele. E két tétel egy optimális kombinációját bizonyítjuk.

Megmutatjuk, hogy ha adott egy $F$ család $n$ konvex halmazzal $\mathbb{R}^d$-ben úgy, hogy legalább $\alpha \binom{n}{d+1}$ darab $(d+1)$-es részcsalád metszete legalább 1 térfogatú, akkor kiválasztható $\Omega_{d,\alpha}(n)$ elem $F$-ből, melyek metszete legalább $\Omega_d(1)$ térfogatú.

Közös munka Frankl Nórával és Tomon Istvánnal.

2025. március 7. (10:15)
Riesz terem
Imolay András
ELTE

On Finding Zero and Non-Zero Bases and Common Bases in Group-Labeled Matroids

Many combinatorial optimization problems involve additional constraints, including parity, congruence, and exact-weight constraints. These constraints can be expressed in a unified way by considering a labeling of the underlying set by the elements of a group, and looking for a solution where the sum of the labels of its entries is a prescribed group element. A special case of interest is when the prescribed element is 0, which we refer to as the zero constraint. Furthermore, in path and cycle problems on graphs, the non-zero constraint is also of interest.

Matroids play a fundamental role in combinatorial optimization. However, the study of zero and non-zero constraints in matroid problems has received surprisingly little attention. Our research aims to fill this gap by developing a theory of zero and non-zero constraints in matroid optimization. More concretely, we focus on the Zero Basis, Non-Zero Basis, Zero Common Basis, and Non-Zero Common Basis problems, and we also consider their weighted extensions. Our main goal is to decide which problems are hard, and which can be solved in polynomial time.

While finding a non-zero basis and a minimum-weight non-zero basis is not difficult, it turns out that the tractability of the Non-Zero Common Basis problem highly depends on the structure of the group. Specifically, a polynomial-time algorithm exists if and only if the group has no element of order two. In contrast, we prove that the weighted case is hard for any nontrivial group. The problem of finding zero bases and zero common bases turns out to be more difficult than finding their non-zero counterparts.

I will finish my talk with some interesting generalizations and open problems. Joint work with Florian Hörsch, Taihei Oki and Tamás Schwarcz.

2025. február 21. (10:15)
Riesz terem
Hegyvári Norbert
Rényi Intézet, ELTE

Néhány kombinatorikus számelméleti tételről; ergodelmélet vs. Ramsey tételek

Az 1970-es évektől igen gyümölcsözóen használható kombinatorikus számelméletben az ergodelmélet, melyet H. Fürstenberg, V. Bergelson és mások indítottak el (Fürstenberg adta a Szemerédi tétel második bizonyítását).

Az előadásban Bergelson egy szép tételét --- nevezetesen, hogy egy "sűrű" sorozat különbséghalmaza bővelkedik aritmetikai tulajdonsággal -- fogunk elemi/kombinatorikus megközelítésben bizonyítani. (E tételre teljesen kombinatorikus bizonyítást én adtam, később Ruzsával egy harmadik bizonyítást is adtunk).

Az előadás második felében egy bonyolultságelméleti kérdést is vizsgálunk, melyben egy érdekes párosítási tételt használunk. A felhasznált eszközök Ramsey, Erdős-Radó, van der Waerden típusú tételek lesznek.

2025. február 7. (10:15)
Riesz terem
Barát János
Rényi Intézet, Pannon Egyetem

Ramsey kérdések rendezett csúcshalmazon

Egy teljes gráf éleit színezzük 2 színnel. Ismert, hogy ekkor található monokromatikus feszítőfa. Hány csúcsú teljes gráfot kell venni ahhoz, hogy m élű monokromatikus párosítást találjunk? Mi ismert más részstruktúrákra? Utakra, körökre.
Tekinthetjük a fenti problémákat geometriai gráfokon vagy topológikus gáfokon. Ekkor olyan monokromatikus részeket keresünk, melynek élei páronként nem metszők. Ennek egy speciális esete a twisted gráf, mikor a lehető legtöbb metszéssel van lerajzolva az alapgráf. Ez vezetett el minket arra, hogy a kérdést rendezett csúcshalmazon vizsgáljuk.

Vegyünk az 1,2...,k rendezett halmazon egy teljes gráfot. Két él kölcsönös helyzete háromféle lehet: szeparált, metsző vagy ölelkező. Ezek alapján 6-féle megszorítást tehetünk a keresett monokromatikus részstruktúrára. Ezekről a kérdésekről fogok beszélni.
Közös eredmények Gyárfás Andrással, Tóth Gézával

2024. november 15. (10:30)
Riesz terem
Recski András
BMGE

Gráfelmélet a statikában

A rúdszerkezetek merevségének vizsgálata fontos kérdés a statikában. Ennek során már Maxwell (1864) is gráfelméleti eszközöket használt és az utóbbi fél évszázadban különösen sok érdekes eredmény született.
Az előadás (mely semmilyen statikai előismeretet nem igényel) ezekből mutat be néhányat és nyitott problémákat is ismertet.

2024. november 8. (10:00)
Riesz terem
Patkós Balázs
Rényi Intézet

Uniform and non-uniform set system problems for disjointness patterns

The most number of sets without two of them being disjoint was determined by Erdős, Ko, and Rado both in the uniform and in the non-uniform case. The most number of sets in a set system without $s$ pairwise disjoint sets is not completely determined neither in the uniform case (Erdős matching conjecture) nor in the non-uniform case (Kleitman's problem).
In this talk, I shall give a brief history of these problems, show some new results, and introduce a general setting for considering disjointness patterns. Based on joint work with Ryan Martin.

2024. október 25. (10:30)
Riesz terem
Csaba Béla
SZTE Bolyai Intézet

Hamilton-körök diszkrepanciája

A kombinatorikus diszkrepancia alapkérdése (kissé pongyolán megfogalmazva) a következő:

Egy véges $X$ halmazon meg van adva egy $S$ halmazrendszer. Az $X$ halmaz elemeit két színnel színezzük - mekkora a maximális "színbeli kiegyensúlyozatlanság", amit nem tudunk elkerülni $S$ élein, akárhogy is színezzük $X$ elemeit? Nemcsak számos cikk, könyvek is születtek már diszkrepancia elméletből.
A feladat antidiszkrepancia változata: keressünk olyan $S$ élt, aminek a kiegyensúlyozatlansága kicsi, akármi is a színezés!

Legyen most $V$ egy $n$ elemű halmaz, $G$ egy egyszerű gráf $V$ ponthalmazzal. A fenti $X$ halmaz szerepét $G$ élei játsszák, az $S$ halmazrendszer élei pedig $G$ Hamilton-körei. Tehát színezzük $G$ éleit, és keresünk nagy/kicsi diszkrepanciájú Hamilton-kört.
Az utóbbi években több diszkrepancia témájú cikk jelent meg ebben a kérdéskörben, hipergráfos változatokat is vizsgálnak már.

A kérdés egy újabb változatában nem színezünk. Ehelyett a $G$ gráf irányított, és olyan Hamilton-kört keresünk, amiben az élek többsége a kör egy körüljárásával megegyező irányú (diszkrepancia), illetve olyat, amiben közel ugyanannyi él található mind a két irányban (antidiszkrepancia).

Friss eredmény (Freschi és Lo), hogy ha $G$ (irányítatlan) minimális foka $\ge n/2 + k$ ($k>0$ egész), akkor van olyan Hamilton-kör, amin legalább $n/2+k$ él ugyanabba az irányba mutat. Tehát a diszkrepanciája $\ge 2k$. Ez az állítás éles.

London András egy új eredménye: ha a fenti $k=\Omega(n^{2/3}\sqrt{\log n})$, akkor van legfeljebb $O(n^{2/3})$-os antidiszkrepanciájú Hamilton-kör.
Ennek az eredménynek egy javításáról lesz szó:
ha $k\ge500$ ($500$ garantáltan elég nagy itt), tehát $G$ (irányítatlan) minimális foka legalább $n/2+500$, akkor van $G$-nek olyan Hamilton-köre, amiben legfeljebb $1000$ az ellenkező irányba mutató élek számának különbsége, azaz az antidiszkrepancia. A tétel Ryan Martinnal közös munka eredménye.

Fontos szegedi vonatkozás: a fenti gráfelméleti diszkrepancia vizsgálatok ötletadója, elindítója, többször szerzője kollégánk, Pluhár András.

2024. október 18. (10:30)
Riesz terem
Gujgiczer Anna
Rényi Intézet

Gráfkódok

Két, azonos csúcshalmazon definiált, $G_1$ és $G_2$ gráf szimmetrikus differenciája az a gráf, melynek csúcshalmaza megegyezik a $G_1$ és $G_2$ gráfok csúcshalmazával, és amelynek éleit azok a csúcspárok alkotják, melyek a $G_1$ és $G_2$ gráfok pontosan egyikében szomszédosak.

Érdekes megvizsgálni, hogy egy $n$ méretű közös csúcshalmazon legfeljebb mennyi gráf adható úgy, hogy közülük bármely kettő szimmetrikus differenciája kielégítsen valamilyen előírt feltételt. Ha például azt a feltételt választjuk, hogy ez a differencia legalább $d$ élet tartalmazzon, akkor visszakapjuk a klasszikus kódelméleti kérdést: Legfeljebb mennyi $m$ hosszú bináris kód adható úgy, hogy közülük bármely kettő legalább $d$ helyen különbözzön? Meggondolható, hogy $m = \binom{n}{2}$ választással ez tényleg ugyanaz a probléma, ha a bináris kódokra úgy tekintünk, mint az $n$ csúcsú gráfok élhalmazait leíró karakterisztikus vektorokra.

Azonban vizsgálhatunk általánosabb tulajdonságokat is, mint például az összefüggőséget vagy azt, hogy van-e Hamilton-út a gráfban vagy akár egy-egy rögzített részgráf tartalmazását is.

Ebben az előadásban néhány eredményt szeretnék ismertetni egy erről a problémakörről szóló cikkünkből, melynek társszerzői Alon, Körner, Milojević és Simonyi.

2024. október 11. (10:00)
Riesz terem
Blázsik Zoltán
SZTE Bolyai Intézet

Irányítatlan gráfok megirányítható totális dominálási száma

Az irányítatlan gráfok esetén domináló halmaznak nevezzük a csúcsok egy részhalmazát, ha minden rajtuk kívüli csúcsnak létezik szomszédja a domináló halmazból. Totálisan dominálónak pedig pontosan akkor, ha a gráf bármely csúcsára igaz ez, azaz ha a szomszédságok uniója lefedi a csúcshalmazt. A minimális méretű domináló/totálisan domináló halmaz méretét a gráf dominálási/totális dominálási számának nevezzük.

Irányított gráfok esetén a két fogalom analóg módon általánosítható, de egy csúcs csak azokat a csúcsokat "dominálja", amikbe vezet belőle él. Az irányított értelemben vett dominálási/totális dominálási szám is analógan definiálható.

Ha adott egy $G$ irányítatlan gráf, akkor a (felső) megirányítható totális dominálási száma (upper orientable total domination number) az a szám, ami a maximuma azoknak az irányított értelemben vett totális dominálási számoknak, ahol az irányított gráfot úgy kapjuk, hogy vesszük az irányítatlan gráf összes lehetséges megirányítását.

Szeretnék az ÚNKP témavezetettemmel közös kutatásról mesélni, amiben azt az esetet vizsgáljuk, amikor ez a megirányítható totális dominálási szám közel van a gráf csúcsszámához.