Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Half-integral Erdos-Posa Property for Non-null Cycles
200
0
0.0
(
0
)
Added by
Ramanujan M. S.
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A Group Labeled Graph is a pair $(G,Lambda)$ where $G$ is an oriented graph and $Lambda$ is a mapping from the arcs of $G$ to elements of a group. A (not necessarily directed) cycle $C$ is called non-null if for any cyclic ordering of the arcs in $C$, the group element obtained by `adding the labels on forward arcs and `subtracting the labels on reverse arcs is not the identity element of the group. Non-null cycles in group labeled graphs generalize several well-known graph structures, including odd cycles. In this paper, we prove that non-null cycles on Group Labeled Graphs have the half-integral Erdos-Posa property. That is, there is a function $f:{mathbb N}to {mathbb N}$ such that for any $kin {mathbb N}$, any group labeled graph $(G,Lambda)$ has a set of $k$ non-null cycles such that each vertex of $G$ appears in at most two of these cycles or there is a set of at most $f(k)$ vertices that intersects every non-null cycle. Since it is known that non-null cycles do not have the integeral Erdos-Posa property in general, a half-integral Erdos-Posa result is the best one could hope for.
rate research
Read More
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)$ hitting all directed odd cycles. This extends the half-integral ErdH{o}s-Posa property of undirected odd cycles, proved by Reed [Mangoes and blueberries. Combinatorica 1999], to digraphs.
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 the ErdH{o}s-Posa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either $k+1$ vertex-disjoint chordless cycles, or $c_1k^2 log k+c_2$ vertices hitting every chordless cycle for some constants $c_1$ and $c_2$. It immediately implies an approximation algorithm of factor $mathcal{O}(sf{opt}log {sf opt})$ for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least $ell$ for any fixed $ellge 5$ do not have the ErdH{o}s-Posa property.
A minor-model of a graph $H$ in a graph $G$ is a subgraph of $G$ that can be contracted to $H$. We prove that for a positive integer $ell$ and a non-empty planar graph $H$ with at least $ell-1$ connected components, there exists a function $f_{H, ell}:mathbb{N}rightarrow mathbb{R}$ satisfying the property that every graph $G$ with a family of vertex subsets $Z_1, ldots, Z_m$ contains either $k$ pairwise vertex-disjoint minor-models of $H$ each intersecting at least $ell$ sets among prescribed vertex sets, or a vertex subset of size at most $f_{H, ell}(k)$ that meets all such minor-models of $H$. This function $f_{H, ell}$ is independent with the number $m$ of given sets, and thus, our result generalizes Maders $mathcal S$-path Theorem, by applying $ell=2$ and $H$ to be the one-vertex graph. We prove that such a function $f_{H, ell}$ does not exist if $H$ consists of at most $ell-2$ connected components.
According to the ErdH{o}s discrepancy conjecture, for any infinite $pm 1$ sequence, there exists a homogeneous arithmetic progression of unbounded discrepancy. In other words, for any $pm 1$ sequence $(x_1,x_2,...)$ and a discrepancy $C$, there exist integers $m$ and $d$ such that $|sum_{i=1}^m x_{i cdot d}| > C$. This is an $80$-year-old open problem and recent development proved that this conjecture is true for discrepancies up to $2$. Paul ErdH{o}s also conjectured that this property of unbounded discrepancy even holds for the restricted case of completely multiplicative sequences (CMSs), namely sequences $(x_1,x_2,...)$ where $x_{a cdot b} = x_{a} cdot x_{b}$ for any $a,b geq 1$. The longest CMS with discrepancy $2$ has been proven to be of size $246$. In this paper, we prove that any completely multiplicative sequence of size $127,646$ or more has discrepancy at least $4$, proving the ErdH{o}s discrepancy conjecture for CMSs of discrepancies up to $3$. In addition, we prove that this bound is tight and increases the size of the longest known sequence of discrepancy $3$ from $17,000$ to $127,645$. Finally, we provide inductive construction rules as well as streamlining methods to improve the lower bounds for sequences of higher discrepancies.
Robertson and Seymour proved that the family of all graphs containing a fixed graph $H$ as a minor has the ErdH{o}s-Posa property if and only if $H$ is planar. We show that this is no longer true for the edge version of the ErdH{o}s-Posa property, and indeed even fails when $H$ is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
