Erdős–Pósa theorem
Encyclopedia
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 such for each positive integer , every graph either contains vertex-disjoint circuits
or it has a feedback vertex set
of vertices that intersects every circuit. Furthermore, in the sense of Big O notation
. Because of this theorem, circuits are said to have the Erdős–Pósa property.
, which states that . obtained the bounds for the general case. The result suggests that although there are infinitely many different graphs with no disjoint circuits, they split into finitely many simply describable classes. For the case , gave a complete characterization. proved and .
s is defined to have the Erdős–Pósa property if there exists a function such that for every (hyper-)graph and every integer one of the following is true:
contains vertex-disjoint subgraphs each isomorphic to a graph in ; or contains a vertex set of size at most such that has no subgraph isomorphic to a graph in .
The definition is often phrased as follows. If one denotes by the maximum number of vertex disjoint subgraphs of isomorphic to a graph in and by the minimum number of vertices whose deletion from leaves a graph without a subgraph isomorphic to a graph in , then , for some function not depending on .
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Erdős–Pósa theorem, named after Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Lajos Pósa
Lajos Pósa (mathematician)
Lajos Pósa is a Hungarian mathematician, working in combinatorics. Paul Erdős's favorite "child", he discovered theorems at the age of 16. Since 2002 he works at the Rényi Institute of the Hungarian Academy of Sciences; earlier he was at the Eötvös Loránd University, at the Departments of...
, states that there is a function such for each positive integer , every graph either contains vertex-disjoint circuits
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
or it has a feedback vertex set
Feedback vertex set
In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph....
of vertices that intersects every circuit. Furthermore, in the sense of Big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
. Because of this theorem, circuits are said to have the Erdős–Pósa property.
Erdős–Pósa theorem
The theorem claims that for any finite number there is an appropriate (least) value , with the property that every graph with no vertex-disjoint circuits all circuits can be covered by vertices. This generalized an unpublished result of Béla BollobásBéla Bollobás
Béla Bollobás FRS is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory and percolation. As a student, he took part in the first three International Mathematical Olympiads, winning two gold medals...
, which states that . obtained the bounds for the general case. The result suggests that although there are infinitely many different graphs with no disjoint circuits, they split into finitely many simply describable classes. For the case , gave a complete characterization. proved and .
Erdős–Pósa property
A family of graphs or hypergraphHypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
s is defined to have the Erdős–Pósa property if there exists a function such that for every (hyper-)graph and every integer one of the following is true:
contains vertex-disjoint subgraphs each isomorphic to a graph in ; or contains a vertex set of size at most such that has no subgraph isomorphic to a graph in .
The definition is often phrased as follows. If one denotes by the maximum number of vertex disjoint subgraphs of isomorphic to a graph in and by the minimum number of vertices whose deletion from leaves a graph without a subgraph isomorphic to a graph in , then , for some function not depending on .