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?