Let $ex_P(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, $ex_P(n,T,H)$ is the planar Turán number of $H$, denoted by $ex_P(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016) [1]. He obtained sharp upper bound for both $ex_P(n,C_4)$ and $ex_P(n,C_5)$. In [2], we gave a sharp upper bound $ex_P(n,C_6) \le \frac{5n}{2} − 7$ for all $n \ge 18$.
We proved that for every integer $n \ge 6$, $ex_P(n,C_5,\emptyset)$ is $2n^2−10n+12+(1)$ (see [3]). And (see [4]), for every fixed $k \ge 3$, $ex_P(n,C_{2k},\emptyset)$ is $\frac{n^k}{k^k} + o(n^k)$. In this lecture, we present more recent similar results related to cycles and paths, and say a few words about the proof techniques.
[1] C. Dowden. Extremal $C_4$-free/$C_5$-free planar graphs. Journal of Graph Theory 83 (2016), 213-230.
[2] D. Ghosh, E. Győri, R. R. Martin, A. Paulos, C. Xiao. Planar Turán Number of the 6-Cycle. SIAM Journal on Discrete Mathematics 36 (3) (2022), 2028-2050.
[3] E. Győri, A. Paulos, N. Salia, C. Tompkins, O. Zamora. The maximum number of pentagons in a planar graph. J. Graph Th., 108 (2025). pp. 229-256.
[4] Z. Lv, E. Győri, Z. He, N. Salia, C. Tompkins, X. Zhu. The maximum number of copies of an even cycle in a planar graph. J. Combinatorial Th. B, 167 (2024) 15-22.
While the classic Rubik's Cube (along with some of its highly symmetric variants) can be described using groups, most twisty puzzles are inherently too irregular to be modeled this way. Our goal is to build a formal framework for analyzing the widest possible variety of twisty puzzles through their state spaces, with the help of graph and group theory. After assuming some fundamental geometric properties, we define a natural simple digraph for twisty puzzles, and establish the graph theoretical conventions that follow from our observations. Using these conventions, we examine the automorphisms of state space graphs to construct a reduced graph defined for each orbit of nodes, and prove these are Cayley-graphs. Then we factor the state space graph by the orbit classes to consider how the orbit classes interconnect, producing the quotient graph colloquially known as the shape space. Next, we utilize these two derived graphs to get a path between any two nodes within the state space graph, thus providing a solution method for the puzzle in question. Finally, we translate the key properties of certain classes of twisty puzzles into state space graph identities, in order to lay the groundwork for future research.
Let $G$ be a graph of minimum degree at least $v(G)/2$. Can we color the edges of~$G$ with red and blue so that every non-adjacent pair of vertices is connected by a path consisting of $exactly$ one red edge and one blue edge? In this talk, we provide an affirmative answer when $G$ is ``close'' to a complete balanced bipartite graph or the disjoint union of two cliques of the same order. We also discuss an asymptotic version of this question.
This is joint work with János Barát and Andrea Freschi.
Egy gráf részleges élszínezésének kiterjesztése alatt azt értjük, hogy a gráf éleinek egy részhalmazát jól színezve mikor egészíthető ki ez az előszínezés a teljes gráf jó élszínezésévé úgy, hogy nem használunk a megengedettnél (jellemzően a kromatikus indexnél) több színt. Röviden áttekintjük a probléma hátterét és néhány klasszikus eredményt, majd Descartes-szorzatokra, illetve speciális esetként hiperkockákra vonatkozó kiterjesztési tételeket tárgyalunk.
Az előadás középpontjában olyan eredmények állnak, amelyekben az előszínezett élek egymástól való távolságára teszünk feltételeket. Páros gráfok Descartes-szorzatában egy természetes fokszámfeltétel mellett a 3-távolságú párosítások, hiperkockákban pedig 2-távolságú párosítások előszínezésének kiterjeszthetőségét igazoljuk.
Az eredmények Győri Ervinnel közösek.
A directed graph is called acyclic if it contains no directed circuit, and totally cyclic if every arc belongs to a directed circuit. For a graph $G$, let $\tau(G)$, $a(G)$, and $c(G)$ denote, respectively, the numbers of spanning trees, acyclic orientations, and totally cyclic orientations of $G$. The Merino–Welsh conjecture states that $\tau(G)\leq \max{a(G),c(G)}$ for every bridgeless and loopless multigraph $G$.
In this talk, we will briefly discuss the history of the conjecture and its connection with the Tutte polynomial. We will then present improved bounds on the edge density that guarantee the conjecture in the sparse and dense regimes.
Egy $n$-változós Boole-függvény érzékenysége egy adott $x$ inputon azon bitjeinek száma, amit megváltoztatva a függvény értéke is megváltozik. A függvény érzékenysége a legnagyobb érzékenység a $2^n$ input között. A blokk-érzékenység ennek egy általánosítása: bitek helyett bit-blokkok megfordításával kell az értéket megváltoztatni és a páronként diszjunkt blokkok számát maximalizáljuk. Technikailag nagyon hasznos fogalom legalább akkora mint az érzékenység. Sokan azt gondolták, hogy sokkal nagyobb nem is lehet.
Szegedy és Nisan 1994-ben sejtette, hogy az érzékenység és blokk-érzékenység közötti kapcsolat polinomiális. Több mint 25 évig a sejtés egy központi megoldatlan probléma volt. 2019-ben Huang megoldotta a sejtést egyszerű érveléssel, ami BSc-s lineáris algebrai ismeretekre támaszkodott.
Az előadás a kérdés hátteréről, példákról és a megoldásról szól.
Egy izolált csúcsoktól mentes $G$ gráfban az $S\subseteq V$ ponthalmaz totálisan domináló, ha minden $V$-beli csúcsnak van $S$-beli szomszédja. Azt mondjuk két csúcsrészhalmazra $X,Y\subseteq V$, hogy ők totális koalíciót alkotnak, ha egyikük sem totálisan domináló halmaz, de $X\cup Y$ már az.
A $G$ gráf $\Psi=\{V_1,V_2,\dots,V_k\}$ csúcspartíciója egy totális koalíció partíció, ha tetszőleges $V_i$-hez létezik olyan $V_j$, amivel együtt ők totális koalíciót alkotnak. Jelölje $C_t(G)$ azt a legnagyobb $k$ egész számot, amire létezik $k$ osztályú totális koalíció partíció. Ezt nevezzük a $G$ gráf totális koalíció számának.
Barát és Blázsik éles alsó és felső korlátot bizonyítottak a totális koalíció számra a gráf maximális és minimális fokszámának segítségével, amiből 3-reguláris gráfokra az következik, hogy $4\le C_t(G)\le 6$. A mostani előadásban arra fókuszálnék, amit ezek után Michael A. Henninggel és közösen témavezetett doktoranduszunkkal (Shahin N. Jogan) együtt csináltunk karommentes, $3$-reguláris gráfok totális koalíció számával kapcsolatban.