ﻻ يوجد ملخص باللغة العربية
ErdH{o}s and P{o}sa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.
We prove that there exists a function $f:mathbb{N}rightarrow mathbb{R}$ such that every digraph $G$ contains either $k$ directed odd cycles where every vertex of $G$ is contained in at most two of them, or a vertex set $X$ of size at most $f(k)$ hitt
We provide a cyclic permutation analogue of the ErdH os-Szekeres theorem. In particular, we show that every cyclic permutation of length $(k-1)(ell-1)+2$ has either an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permu
We extend the famous ErdH{o}s-Szekeres theorem to $k$-flats in ${mathbb{R}^d}$
A graph is $P_8$-free if it contains no induced subgraph isomorphic to the path $P_8$ on eight vertices. In 1995, ErdH{o}s and Gy{a}rf{a}s conjectured that every graph of minimum degree at least three contains a cycle whose length is a power of two.
A chordless cycle, or equivalently a hole, in a graph $G$ is an induced subgraph of $G$ which is a cycle of length at least $4$. We prove that the ErdH{o}s-Posa property holds for chordless cycles, which resolves the major open question concerning th