Bastide, Groenland and Nenadov showed that there is a poset $P$ of size $ 2^{\left(1+o(1)\right)2n/3}$, which is universal for the family of $n$-element posets. We improve upon their result, by providing such universal poset of size $2^{(1+o(1))n/2}$.
This result is a step towards the conjectured minimum size $2^{(1+o(1))n/4}$. It is joint work with Ramon I. Garcia and Marcelo Sales.
Tekintsünk egy $n$ szögpontú gráfot, valamint egy test $n$ darab véges részhalmazát, melyeket a csúcspontokhoz rendelünk. Ezekből úgy képzünk $n$-tagú összegeket, hogy két összeadandó nem lehet egyenlő, ha a nekik megfelelő csúcsokat a gráfban él köti össze. A polinom-módszer segítégével Wang és Sun pár éve éles alsó becslést adott az összeghalmaz méretére abban az esetben, ha a halmazok mérete megegyezik, a gráf pedig út, vagy páros hosszú kör.
Az ún. együttható lemma lehetőséget ad arra, hogy átláthatóbb bizonyítást adjunk ezekre az eredményekre, enyhítsünk a test karakterisztikájára tett megkötésen, valamint páratlan körök esetén is igazoljuk a sejtett alsó korlátot. Módszerünk utak hatványaira is alkalmazható, miáltal bepillantást nyerhetünk abba, milyen módon csökken az összeghalmaz lehetséges legkisebb mérete, miközben eljutunk a Cauchy-Davenport tételtől a Dias da Silva-Hamidoune tételig.
An edge $e$ of the graph $G$ is crossing critical if its removal decreases the crossing number of the graph, i.e. $cr(G-e)< cr(G)$. It is clear that if an edge $e$ is crossed an an optimal drawing of $G$, $e$ is crossing critical.
Kuratowski theorem states that a graph is nonplanar precisely when it contains a subdivision of a $K_5$ or a $K_{3,3}$. Subgraphs that are subdivided $K_5$ or subdivided $K_{3,3}$ are Kuratowski subgraphs, an edge is a Kuratowski edge if it is in a Kuratowski subgraph, and a Kuratowski edge is a strong Kuratowski edge if it is in every Kuratowski subgraph. Kuratowski theorem implies that strong Kuratowski edges are crossing-critical.
We consider the following questions: If an edge is crossed in every optimal drawing of the graph, is it a Kuratowski edge? If an edge is a strong Kuratowski edge, is it crossed in some optimal drawing of the graph? If an edge is not a Kuratowski edge and is not crossed in any optimal drawing, can it be crossing critical?
This is joint work with Alec Helm.
Much attention has been paid to infinite planar graphs. We investigate the ordinary crossing numbers of infinite graphs. Building heavily on the theory of infinite planar graphs, and slightly extending it to multigraphs, we study graph embeddings, graph drawings, and crossing numbers of infinite graphs. We investigate what kind of properties can be forced on optimal drawings, including the avoidance of certain kinds of accumulation points which can emerge in drawings of infinite graphs. Among other results, we extend the equality of planar and spherical crossing numbers to infinite graphs, classify outerplanar graphs, and prove compactness results for the crossing number of countable graphs and the $k$-page crossing numbers of countable graphs.
A sample result is that on the 2-page book, continuum many even cycles can be drawn without crossing, but not uncountably many odd cycles.
Joint work with Eva Czabarka and Alec Helm.
A klikk játékban két játékos közösen épít egy gráfot. A gráf eredetileg üres, majd a két játékos felváltva lép: - Építő hozzáad a gráfhoz egy új csúcsot, azt összeköti az összes többi csúccsal, majd a keletkezett gráf éleit tetszőlegesen két részre bontja. - Romboló a két rész közül az egyikben szereplő összes élet kitörli a gráfból. Építő nyer, ha sikerül egy 100 csúcsú klikket létrehoznia. Romboló célja ezt megakadályozni, vagy legalább addig elodázni, amíg bírja.
A véletlen módszer egyik első alkalmazásaként Erdős Pál belátta, hogy léteznek nagy girth-ű nagy kromatikus számú gráfok. Precízebben: tetszőleges pozitív $g$ és $k$ esetén létezik olyan $k$-kromatikus véges gráf, aminek nincs $g$-nél rövidebb köre. Hajnal Andrással azt sejtették, hogy nem hogy csak léteznek ilyen gráfok, de minden nagy kromatikus számú gráfban benne vannak: minden $g$-hez és $k$-hoz van $N$, hogy minden $N$-kromatikus gráfnak van $k$-kromatikus részgráfja, aminek nincs $g$-nél rövidebb köre. A $g=4$ (háromszögmentes) esetet Vojtěch Rödl belátta, nagyobb girth esetén azonban a sejtés nyitott.
Tud Építő nyerni a Klikk játékban? Ha igen, hány lépés alatt? És mi köze ennek az Erdős-Hajnal sejtéshez? Ezt próbálom megvilágítani az előadással, amely egy Bartosz Walczakkal és Seth Pettievel közös cikkre épül.
Ebben az előadásban az úgynevezett MP-arányt vizsgáljuk, amely egy adott véges szó palindromikusságának mértékét fejezi ki. Az MP-arány definíció szerint az MP-kiterjesztés hosszának és az eredeti szó hosszának hányadosa, ahol az MP-kiterjesztés – leegyszerűsítve – egy olyan szó, amely nem tartalmaz a szükségesnél hosszabb palindromikus részszavakat.
Megvizsgálunk néhány, az MP-arányra vonatkozó korlátot, valamint azt, hogy ezek a becslések miként függnek a szavak ábécéjének méretétől. Bemutatunk továbbá néhány alapvető bizonyítási technikát is, amelyek ezekhez az eredményekhez vezetnek. Végül áttekintjük, milyen kérdések maradtak még nyitva, és milyen irányokban érdemes a további vizsgálatokat folytatni.
Közös munka Bojan Bašićtyal.
For every $d\geq 2$, we construct a subset $\Gamma\subseteq \{1,\dots,n\}^d$ of size $n-o(n)$ in general position (i.e. every affine hyperplane of $\mathbb{R}^d$ intersects $\Gamma$ in at most $d$ points) such that every hypersphere of $\mathbb{R}^n$ intersects $\Gamma$ in at most $d+1$ points. This construction is the largest one currently known for the $d$-dimensional general position no-$(d+2)$-on-a-sphere problem (originating from Erdős and Purdy), and improves Thiele's $\frac{3}{32}n^{1/(d-1)}$, and the recent $\frac{1}{d+1}n-o(n)$ bound of Dong and Xu.
More generally, we prove that the role of hyperspheres above can be replaced by $Q$-quadrics, i.e. by quadratic surfaces given by a polynomial whose degree two homogeneous part equals a fixed quadratic form $Q$. Furthermore, we formulate analogous statements in affine spaces over (finite) fields.
These constructions are all based on a suitable rational normal curve in a $d$-dimensional projective space obtained by generalising the ideas of Dong, Xu, and Thiele.
Available at https://arxiv.org/abs/2511.03526.
In this talk, we will share two new problems about cages.
A cage is a regular graph with a given girth (the length of the shortest cycle) and the minimum number of vertices. The cage problem was posed in 1947 by Tutte, who asked about the minimum order of cubic graphs with fixed girth. The problem was later generalized to any degree, and in 1963, Erdős and Sachs proved their existence. Since then, this problem has been widely studied.
In this talk, Linda Lesniak will relate this problem to the chromatic number, which is the minimum number of colors needed to color the vertices of a graph so that no adjacent vertices share the same color. There is a conjecture stating that cages of even girth are bipartite. We ask about the existence of the smallest regular graphs with even girth that are not bipartite; that is, we consider regular graphs of even girth, chromatic number 3, and minimum order. More generally, given three parameters $r \geq 2$, $g \geq 3$, and $\chi \geq 3$ (degree, girth, and chromatic number), we ask for graphs of minimum order with these parameters, or the $(r,g;\chi)$-cages.
Also, in this talk, Gabriela Araujo introduces a new problem that she and György Kiss have studied very recently, about the existence and constructions of balanced biregular cages. They are bi-regular graphs (graphs with two degrees $r$ and $s$), but with the property that they have the same number of vertices of degree $r$ as vertices of degree $s$, and also with minimum order.
Egy ismert gráfelméleti eredmény szerint egy Euler-féle irányított gráfban bármilyen gyökérponttal ugyanannyi feszítő fenyő van. Erre a tételre mutatunk egy geometriai bizonyítást. Ehhez egy poliédert fogunk definiálni, amelynek a térfogata adja meg a kérdéses számot. Sőt, a poliéder segítségével az úgynevezett greedoid polinomra is tudunk geometriai definíciót adni. Ha marad idő, beszélni fogok a témának a speciális alternáló csomók Alexander-polinomjához való kapcsolatáról is
In the affine space $\mathbb{F}_q^n$ over the finite field of order $q$, a point set $S$ is said to be $(d,k,r)$-evasive if the intersection between $S$ and any variety, of dimension $k$ and degree at most $d$, has cardinality less than $r$. As $q$ tends to infinity, the size of a $(d,k,r)$-evasive set in $\mathbb{F}_q^n$ is at most $O\left(q^{n-k}\right)$ by a simple averaging argument.
We exhibit the existence of such evasive sets of sizes at least $\Omega\left(q^{n-k}\right)$ for much smaller values of $r$ than previously known constructions, and establish an enumerative upper bound $2^{O(q^{n-k})}$ for the total number of such evasive sets. The existence result is based on our study of twisted varieties. In the projective space $\mathbb{P}^n$ over an algebraically closed field, a variety $V$ is said to be $d$-twisted if the intersection between $V$ and any variety, of dimension $n - \dim(V)$ and degree at most $d$, has dimension zero. We prove an upper bound on the smallest possible degree of twisted varieties which is best possible in a mild sense.
The enumeration result includes a new technique for the container method which we believe is of independent interest. To illustrate the potential of this technique, we give a simpler proof of a result by Chen--Liu--Nie--Zeng that characterizes the maximum size of a collinear-triple-free subset in a random sampling of $\mathbb{F}_q^2$ up to polylogarithmic factors.
(Joint work with Jiaxi Nie and Jeck Lim at https://arxiv.org/abs/2507.07594.)
Let $C_k$ be the cycle on $k$ vertices and $H$ be an arbitrary graph on $m$ edges and no isolated vertices. Erd{\H o}s, Faudree, Rousseau and Schelp conjectured that if $m$ is sufficiently large compared to $k$ then the Ramsey number $R(C_k,H)$ is at most $2m+\left\lfloor\frac{k-1}{2}\right\rfloor$. This was verified for $k$ even and for $k\in\{3,5\}$.
In this talk, we present a resolution of all remaining cases, thus confirming the conjecture. This is joint work with Stijn Cambie, Patryk Morawski, Kalina Petrova and Alexey Pokrovskiy
Legyen $G_1, G_2$ két gráf. $G_1$ parkettázható $G_2$ példányokkal, ha le tudunk úgy rakni csúcsdiszjunkt $G_2$-ket $G_1$-be, hogy ne maradjon ki csúcsa $G_1$-nek. Majdnem parkettázható, ha egy "kevés", általában konstans sok, néha kis lineáris számú csúcs kimaradhat.
Verstraete 2002-es sejtése úgy szól, hogy ha G egy $n$ csúcsú $r$-reguláris (minden csúcs foka $r$) gráf, $H$ egy rögzített gráf, akkor van $H$-nak olyan $TH$ felosztása (minden élt helyettesítünk egy $s\ge 2$ hosszú úttal, és $TH$ páros legyen), hogy $G$ majdnem parkettázható $TH$ példányokkal, legfeljebb konstans sok maradhat ki. Pár évvel később Kühn és Osthus belátták a sejtést arra az esetre, ha $r=cn$ valamely $c>0$ konstansra, illetve approximációt adtak arra az esetre, ha $TH$ helyett $H$-val parkettázunk, ahol $H$ páros.
Az utóbbi időben (2025-ben és 2026-ban) megjelent pár cikk, amik igen közel kerültek a sejtésnek, vagy valamely változatának a megoldásához. Montgomery, Petrova, Ranganathan és Tan belátták a sejtés egy approximációs változatát, ha $r$ egy elég nagy konstans. Letzter, Methuku és Sudakov bebizonyították, hogy $H$ példányokkal majdnem parkettázható $G$, csak konstans sok csúcs marad ki, ha $r=cn$ valamely $c>0$ számra. Azt is belátták, hogy ha $r=polylog(n)$, $H$ rőgzített, akkor $TH$ példányokkal majdnem parkettázható $G$, csak $o(n)$ csúcs marad fedetlen $G$-ben.
Ezekről a tételekről és egy ezeket kiegészítő friss eredményemről szeretnék beszélni.
Raimi's theorem guarantees the existence of a partition of $\mathbb{N}$ into two parts with an unavoidable intersection property: for any finite coloring of $\mathbb{N}$, some color class intersects both parts infinitely many times, after an appropriate shift (translation). We extend this result to higher dimension, in fact a stronger form that the traslation will be "polynomial" shifts.
We also prove some finite analogues of the above results for abelian groups and $SL_2(\mathbb{F}_q)$.
This is a joint work with János Pach and Thang Pham.
Az előadás a következő probléma általánosításairól szól: Maximum hány háromszög lehet egy $n$-csúcsú gráfban, amely nem tartalmaz $K_{2,2,1}$-t mint részgráf?
Gyufagráfnak (matchstick graph) hívunk egy olyan, metszés nélkül lerajzolt gráfot, amelynek az élei egység hosszú szakaszok. Egy $n$ csúcsú gyufagráfnak nyilván legfeljebb $3n-6$ éle van. Lavollée és Swanepoel 2024-ben pontosan meghatározta az $n$ csúcsú gyufagráfok maximális élszámát. (Ez $\lfloor 3n-\sqrt{12n-3}\rfloor$). Ennek a meglepő eredménynek különböző érdekes általánosításait, változatait fogjuk vizsgálni.
Többek között bebizonyítjuk a következő, ugyancsak meglepő eredményt. Ha az élek továbbra is egység hosszú szakaszok, de minden él metszhet legfeljebb egy másik élt, akkor az élek maximális száma alig változik (legfeljebb $3n-\sqrt[4]{n}/15$). Sőt, elképzelhető, hogy ez akkor is így van, ha két metszést engedünk élenként.
Közös munka Gehér Pannával, Pach Jánossal és Konrad Swanepoel-lel.
Adott egy $n$ elemű ábécé. Tudjuk, hogy bizonyos betűk megkülönböztethetőek és néhány összetéveszthető. A Shannon-kapacitás azt vizsgálja, hogy aszimptotikusan hány olyan $t$ hosszú szó hozható létre az ábécé felhasználásával, melyek közül bármely két szó megkülönböztethető. Az ábécét tudjuk gráfokkal reprezentálni, viszont a mai napig nyitott kérdés még egyszerű gráfok Shannon-kapacitása is. Például a hét hosszú kör kapacitása sem ismert.
A kapacitás felső becslésére több függvény is ismert: frakcionális kromatikus szám, theta szám, frakcionális Haemers-korlát.
A Mycielski-konstrukció egy olyan gráfoperáció, ami növeli a gráf kromatikus számát eggyel, a klikkszámot pedig nem módosítja. Ez a konstrukció volt az egyik első példa, hogy a távolság a klikkszám és a kromatikus szám között tetszőlegesen nagy lehet.
Célunk, hogy megvizsgáljuk, hogyan hat a Mycielski-konstrukció a Shannon-kapacitást felülről becslő gráfparaméterekre. Az utóbbi években meghatároztuk a theta szám esetén érvényes összefüggést, idén pedig a frakcionális Haemers-korlátra vonatkozó formulát találtunk.
Regularitási módszernek a Regularitási lemma és a Blow-up lemma (beágyazó lemma) együttes használatát szokás hívni. Rendkívül hatékony extremális gráfelméleti kérdésekben, több száz tétel bizonyításának adja a gerincét. Hátránya, hogy a Regularitási lemma csak "csillagászati" méretű gráfokra hasznos igazán.
Az előadásban egy olyan módszert láthatunk, ami a Regularitási lemmát képes kiváltani bizonyos esetekben, úgy, hogy a Blow-up lemma (mely kis gráfokra is érvényes) továbbra is használható legyen. A módszer működésének demonstrálására egy fa beágyazási tétel bizonyítását tekintjük: ha az $n$ csúcsú G gráf minimális foka legalább $n/2 +\varepsilon n$ valamely $\varepsilon >0$-ra, és $T$ egy $n$ csúcsú, korlátos fokú fa, $n$ elég nagy, akkor $T$ feszítőfája $G$-nek.
Ez egy ismert tétel. Bollobás sejtése volt 1978-ból, kb. 20 évre rá bizonyította Komlós, Sárközy és Szemerédi a Regularitási lemma használatával. 2010-ben beláttuk egy Nagy-György Judittal, Ian Levittel és Szemerédi Endrével közös cikkben, már a lemma használata nélkül, viszont így jóval bonyolultabban a tétel első bizonyításánál.
A legújabb bizonyítás előnye, hogy a Regularitási módszer több eleme is átvihető, de "kis" gráfokra is működik. Újdonság még emellett, hogy egy erősebb, ún. stabilitási változatot bizonyítunk: ha $G$ nincs nagyon közel két extremális esethez (két diszjunkt klikk uniója ill. teljes páros gráf), akkor $n/2-\varepsilon n$ -es minimális fokszám is elegendően nagy a tartalmazáshoz.
Egy $G(V,E)$ gráf esetén a $G^{(k)}$ gráf jelölje a $G$ pontos $k$-távolság gráfját, aminek csúcshalmaza megegyezik $V$-vel, és két csúcsot pontosan akkor köt össze él $G^{(k)}$-ban, ha $G$-ben a távolságuk pontosan $k$ volt (a csúcsok címkézettek). Az előadásban vizsgálandó kérdést a következő játék formájában vezetném be: Alice gondol egy egyszerű gráfra, és Bob feladata a gráf rekonstruálása, amihez csupán $k\ge 2$ pozitív egészekre a $G^{(k)}$ pontos $k$-távolságok gráfok egy általa választott részét használhatja.
A rekonstruáláshoz Bobnak lehetősége van elkérnie Alicetól bizonyos $k$ értékekre a gondolt gráf pontos $k$-távolság gráfjait. Az első kérdés az, hogy egyáltalán biztos-e, hogy Bob ki tudja találni a gondolt gráfot. Látjuk majd, hogy ha a gondolt gráf nem feltétlenül összefüggő, akkor nem feltétlenül tudja kitalálni. Ha Alicenak összefüggő gráfra kell gondolnia, akkor igazolható, hogy Bob mindig ki tudja találni a gráfot. (HF)
Megmutatjuk, hogy a triviális kitalálhatóságnál jóval több is igazolható, mindig elég csupán konstans sok $k$-ra elkérni a $G^{(k)}$ gráfokat. Sőt igazolni fogjuk, hogy az eredményünk éles is! Az eredmények Horváth Csongorral és Zsigri Bálinttal közösek.
We investigate the two-graphs associated with strongly regular polar graphs that belong to three infinite classes. Specifically, we examine the strongly regular graph $\Gamma(O^\pm(2m,2))$, which has vertices representing points of a nondegenerate hyperbolic or elliptic quadric $Q^\pm(2m-1,2)$ in the projective space $PG(2m-1,2)$. The set of vertices for $NO^\pm(2m,2)$ is the complement of $Q^\pm(2m-1,2)$. Additionally, we consider the vertices of the third graph $NO^\pm(2m+1,q)$, where $q$ is even, which correspond to hyperplanes of $PG(2m,q)$ that intersect the nondegenerate parabolic quadric in a nondegenerate hyperbolic or elliptic quadric.
Our main result is the proof of switching equivalence for the strongly regular polar graphs $NO^\pm(4m,2)$, $NO^\mp(2m+1,4)$, and $\Gamma(O^\mp(4m,2))$ with an isolated vertex. We establish this by providing an analytic description for these graphs and their corresponding two-graphs.
Adott, esetleg végtelen gráfhoz olyan lokális algoritmusokat vizsgálunk, amelyek a csúcsok által generált véletlen input felhasználásával lokális számolás után csúcsonként adnak ki egy outputot, például egy színezést. Az ilyen osztott számítási problémák keretei hasznosak kombinatorikai és optimalizálási problémákban (például független halmaz keresése véletlen gráfban), valamint valószínűségi modellek generálásában (pl. Ising, Uniform Feszítőerdő).
Az előadás ezen nagy témakör néhány érdekes eredményét ismerteti, és semmilyen előismeretet nem feltételez.
Gráfok maximális független halmazainak számossága klasszikus területe a gráfelméletnek. Az előadás alatt néhány új eredmény lesz ismertetve.
Pár alkalmazást is megemlítünk, például Abel csoportok maximális összegmentes részhalmazainak leszámlálásáról.
A matroidok diszkrét struktúrák, melyek általánosítják a vektorterekben megismert lineáris függetlenség fogalmát. Whitney 1935-ben vezette be a fogalmat, és mára kutatásuk önálló, aktív területté vált. Olyan egységes nyelvezet biztosítanak, melyben sok különböző kombinatorikus és diszkrét optimalizálási kérdést természetes módon lehet megfogalmazni és megoldani. Több különböző ekvivalens axiómarendszerük van, definiálhatjuk őket a független halamzaikon, bázisaikon, vagy - számunkra különösen releváns módon - a rangfüggvényükkel.
A matroidok limeszelméletének kiépítését Lovász kezdte meg 2023-ban azzal, hogy mérhető terekben vizsgálta a szubmoduláris függvények tulajdonságait, és bevezette a gráflimeszelméletben fontos szerepet játszó grafingok körmatroidját. Az eladás során bemutatjuk az azóta történteket: bevezetünk egy konvergenciafogalmat, kapcsolatot építünk gráfoklimeszekkel, és a mérhető világban általánosítunk két véges kombinatorikából ismert állítást.
Az előadás nem feltételez előismereteket sem matroidokról, sem gráflimeszelméletből. Bérczi Kristóffal, Borbényi Mártonnal és Lovász Lászlóval közös munka.
Several measures of phyloghenetic tree balance are known. The Sackin index is one of the oldest and most popular measures of these measures. Recently, extensions of the Sackin index to phylogenetic networks have been proposed in the literature and first results on their statistical properties have been obtained. I will present the extremal values and extremal networks for three variants of the Sackin index and various types of phylogenetic network classes.
A phylogenetic tree with $n$ leaves is a tree, in which every degree is 1 or 3, the degree 1 vertices are labeled bijectively with $1,2,...,n$, and the degree 3 vertices are unlabeled. Distance concepts between phylogenetic trees with $n$ leaves are very relevant, if one wants to speak about 'almost correct' phylogeny reconstruction. Two standard distance concepts are the Robinson-Foulds distance and the quartet distance. There has been great interest in the fast computation of the quartet distance. A 40 years old Bandelt-Dress conjecture is about the asymptotics of the diameter of the tree space in quartet distance.
We introduce a family of $d_i$ distances between phylogenetic trees with $n$ leaves. These are natural generalizations of the previously mentioned distances, such that $d_2$ is the Robinson-Foulds distance and $d_{n-2}$ is the quartet distance. A $k$-partition of $\{1,2,...,n\}$ is {\it induced} by a phylogenetic tree with $n$ leaves, if after the removal of some $k-1$ edges of the tree, the partition classes are each living on a different tree of the remaining forest. The $d_k$ distance between two phylogenetic trees with $n$ leaves depends linearly on the number of common induced $k$-partitions of them. (The induced partitions are often called $convex~characters$, and the common induced partitions $biconvex~characters$ in the phylogenetic literature.)
We proved a number of extremal results for the least number of common $k$-partitions (or partitions) of two phylogenetic trees with $n$ leaves (or two phylogenetic caterpillar trees with $n$ leaves). Bounds on these quantities translate into bounds for the diameter of the tree space (or caterpillar tree space) for the $d_i$ distance.
We extended some results for the least number of common induced $k$-partitions (or partitions) from 2 to $m$ phylogenetic trees with $n$ leaves.
This work was done when EC, VM and LAS were in residence at ICERM, Brown University, at the semester program ''Theory, Methods, and Applications of Quantitative Phylogenomics'', Fall 2024. Joint work with Éva Czabarka, University of South Carolina, Steven Kelk, Maastricht University, Vincent Mouton, University of East Anglia.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
