Erdős–Pósa theorem

Erdős–Pósa theorem This article needs attention from an expert in Mathematics. The specific problem is: Diagrams might help here rather than "big scary words". WikiProject Mathematics may be able to help recruit an expert. (Junho 2020) In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, states that there is a function f(k) such that for each positive integer k, every graph either contains at least k vertex-disjoint cycles or it has a feedback vertex set of at most f(k) vértices. Além disso, f(k) = Θ(k log k) in the sense of Big O notation. Because of this theorem, cycles are said to have the Erdős–Pósa property.

The theorem claims that for any finite number k there is an appropriate (least) value f(k), with the property that in every graph without a set of k vertex-disjoint cycles, all cycles can be covered by no more than f(k) vértices. This generalized an unpublished result of Béla Bollobás, which states that f(2) = 3. Erdős & Pósa (1965) obtained the bounds c1k log k < f(k) < c2k log k for the general case. For the case k = 2, Lovász (1965) gave a complete characterization. Voss (1969) proved f(3) = 6 and 9 ≤ f(4) ≤ 12. Erdős–Pósa property A family F of graphs or hypergraphs is defined to have the Erdős–Pósa property if there exists a function {displaystyle f:mathbb {N} rightarrow mathbb {N} } such that for every (hyper-)graph G and every integer k one of the following is true: G contains k vertex-disjoint subgraphs each isomorphic to a graph in F; or G contains a vertex set C of size at most f(k) such that G − C has no subgraph isomorphic to a graph in F. The definition is often phrased as follows. If one denotes by ν(G) the maximum number of vertex disjoint subgraphs of G isomorphic to a graph in F and by τ(G) the minimum number of vertices whose deletion from G leaves a graph without a subgraph isomorphic to a graph in F, then τ(G) ≤ f(ν(G)), for some function {displaystyle f:mathbb {N} rightarrow mathbb {N} } not depending on G. Rephrased in this terminology, the Erdős–Pósa theorem states that the family F consisting of all cycles has the Erdős–Pósa property, with bounding function f(k) = Θ(k log k). Robertson and Seymour (1986) generalized this considerably. Given a graph H, let F(H) denote the family of all graphs that contain H as a minor. As a corollary of their grid minor theorem, Robertson and Seymour proved that F(H) has the Erdős–Pósa property if and only if H is a planar graph. Moreover, it is now known that the corresponding bounding function is f(k) = Θ(k) if H is a forest (Fiorini, Joret & Wood 2013), while f(k) = Θ(k log k) for every other planar graph H (Cames van Batenburg et al. 2019). The special case where H is a triangle is equivalent to the Erdős–Pósa theorem. References Erdős, Paul; Pósa, Lajos (1965). "On independent circuits contained in a graph". Canadian Journal of Mathematics. 17: 347–352. doi:10.4153/CJM-1965-035-8. S2CID 123981328. Robertson, Neil; Seymour, Paul (1986). "Graph minors. V. Excluding a planar graph". Journal of Combinatorial Theory, Series B. 41: 92–114. doi:10.1016/0095-8956(86)90030-4. Voss, Heinz-Jürgen (1969). "Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten". Mathematische Nachrichten. 40 (1–3): 19–25. doi:10.1002/mana.19690400104. Lovász, László (1965). "On graphs not containing independent circuits". Mat. Lapok. 16: 289–299. Cames van Batenburg, Wouter; Huynh, Tony; Joret, Gwenaël; Raymond, Jean-Florent (2019). "A tight Erdős-Pósa function for planar minors". Advances in Combinatorics. 2: 33pp. doi:10.19086/aic.10807. Fiorini, Samuel; Joret, Gwenaël; Wood, David R. (2013). "Excluded Forest Minors and the Erdős–Pósa Property". Combinatorics, Probability and Computing. 22 (5): 700–721. arXiv:1204.5192. doi:10.1017/S0963548313000266. S2CID 122708. See also Pósa theorem (1962). A list of graph classes for which the Erdös-Pósa property is known to (not) hold. Categories: Theorems in graph theory