RECORD
Analysis of the Lifting Graph
Combinatorics · Submitted 6 Dec 2022
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Here we give a more comprehensive analysis of the structure of the lifting graph.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The `lifting` or `splitting-off` operation on graphs is performed by deleting two edges sv and sw having a common end s and adding a new edge between v and w. Such a lift is considered good if it preserves a certain local edge-connectivity between the pairs of vertices different from the vertex s at which lifting takes place. The operation is important for inductive proofs concerning edge-connectivity, and can be seen widely applied in the literature on connectivity augmentation, network design, orientation (of finite and infinite graphs), and edge-disjoint linkage. It was studied by Lovasz, who used the term splitting-off, and Mader, who used the term lifting. They proved the first two significant results on it, in 1976 and 1978 respectively, showing the existence of a good lift under certain conditions. Then it was used and studied by other researchers, through the 1980s, both for undirected and directed graphs. In particular, it was investigated further by Frank who proved in 1992 that there are floor of deg(s)/2 disjoint good lifts. Motivated by the applications, a new method for studying the operation was introduced by Jordan in the late 1990s. He defined and studied the structure of the `non-admissibility` graph, which is the complement of the lifting graph; the subject of this paper. He proved a number of significant structural results on it, which he applied to connectivity augmentation. Independently, in 2016, Thomassen defined the `lifting graph`, and called its complement the `bad graph`, to apply it in finding orientations of infinite graphs. Later in the same year, Thomassen with Ok and Richter extended the study, and applied their results to linkages in infinite graphs. Here we give a more comprehensive analysis of the structure of the lifting graph.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The `lifting` or `splitting-off` operation on graphs is performed by deleting two edges sv and sw having a common end s and adding a new edge between v and w. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | Such a lift is considered good if it preserves a certain local edge-connectivity between the pairs of vertices different from the vertex s at which lifting takes place. | background 0.99 | 0.04 | 0.03 | asserted 0.98 |
| s2 | The operation is important for inductive proofs concerning edge-connectivity, and can be seen widely applied in the literature on connectivity augmentation, network design, orientation (of finite and infinite graphs), and edge-disjoint linkage. | background 1.00 | 0.05 | 0.03 | asserted 0.98 |
| s3 | It was studied by Lovasz, who used the term splitting-off, and Mader, who used the term lifting. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s4 | They proved the first two significant results on it, in 1976 and 1978 respectively, showing the existence of a good lift under certain conditions. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s5 | Then it was used and studied by other researchers, through the 1980s, both for undirected and directed graphs. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s6 | In particular, it was investigated further by Frank who proved in 1992 that there are floor of deg(s)/2 disjoint good lifts. | background 0.99 | 0.03 | 0.03 | asserted 1.00 |
| s7 | Motivated by the applications, a new method for studying the operation was introduced by Jordan in the late 1990s. | background 0.98 | 0.03 | 0.02 | asserted 1.00 |
| s8 | He defined and studied the structure of the `non-admissibility` graph, which is the complement of the lifting graph; the subject of this paper. | background 0.80 | 0.07 | 0.06 | asserted 1.00 |
| s9 | He proved a number of significant structural results on it, which he applied to connectivity augmentation. | background 0.99 | 0.04 | 0.04 | asserted 1.00 |
| s10 | Independently, in 2016, Thomassen defined the `lifting graph`, and called its complement the `bad graph`, to apply it in finding orientations of infinite graphs. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s11 | Later in the same year, Thomassen with Ok and Richter extended the study, and applied their results to linkages in infinite graphs. | background 1.00 | 0.04 | 0.03 | asserted 1.00 |
| s12 | Here we give a more comprehensive analysis of the structure of the lifting graph. | contribution 1.00 | 0.90 | 0.16 | asserted 0.96 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The `lifting` or `splitting-off` operation on graphs is performed by deleting two edges sv and sw having a common end s and adding a new edge between v and w. Such a lift is considered good if it preserves a certain local edge-connectivity between the pairs of vertices different from the vertex s at which lifting takes place. The operation is important for inductive proofs concerning edge-connectivity, and can be seen widely applied in the literature on connectivity augmentation, network design, orientation (of finite and infinite graphs), and edge-disjoint linkage. It was studied by Lovasz, who used the term splitting-off, and Mader, who used the term lifting. They proved the first two significant results on it, in 1976 and 1978 respectively, showing the existence of a good lift under certain conditions. Then it was used and studied by other researchers, through the 1980s, both for undirected and directed graphs. In particular, it was investigated further by Frank who proved in 1992 that there are floor of deg(s)/2 disjoint good lifts. Motivated by the applications, a new method for studying the operation was introduced by Jordan in the late 1990s. He defined and studied the structure of the `non-admissibility` graph, which is the complement of the lifting graph; the subject of this paper. He proved a number of significant structural results on it, which he applied to connectivity augmentation. Independently, in 2016, Thomassen defined the `lifting graph`, and called its complement the `bad graph`, to apply it in finding orientations of infinite graphs. Later in the same year, Thomassen with Ok and Richter extended the study, and applied their results to linkages in infinite graphs. Here we give a more comprehensive analysis of the structure of the lifting graph.
Human review
How the literature uses it
1 arXiv paper cite this in 6 sentences
Papers citing it · 5 sentences without a confident label
Cites it as background 1 paper
-
( [ref] , [ref] , [ref] ) Let $k$ be a positive integer and $s$ a vertex in a finite graph $G$ such that $G$ is $(s,k)$-edge-connected.
Towards Nash-Williams Orientation Conjecture for Infinite Graphs · Lifting · 0.81
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.