Main Theorems
Theorems and Proofs
This page provides a quick overview to the main theorems and their proofs from the paper. As you go through them, you’ll also find D3 visualizations illustrating each concept. Click on the visualizations for interactive views and better understanding.
content: Let \( G \) be an oriented graph represented by a GLOVER with all nodes the Decreasing Sequence Property (DSP). If all nodes in \( G \) are placed into containers, where interior degrees are maximized, then Seymour's conjecture holds true. Specifically, a node in \( G \) will have its exterior size decrease to less than 2.
proof:
label: Degree Doubling by Exterior Decreasing
proof:
label: Degree Doubling by Exterior Decreasing
content: In an oriented graph \(G\) with minimum degree node \(v_0\) and containers \(C_1, C_2, ..., C_n\), as the containers shrink in size as their distance from the minimum degree node increases, and as the required interior degrees rise, a collision is inevitable. This collision can manifest in two forms: either the size of the container reaches a point where it can no longer support the increasing interior degrees (resulting in nodes that cannot maintain their minimum degree requirements), or smaller containers force a doubling of degrees that contradicts the capacity for interior arcs. The structure of the graph, particularly in small sizes, inherently limits these growth dynamics, leading to contradictions that must be addressed.
proof:
label: Degree Doubling by Container Density
proof:
label: Degree Doubling by Container Density
content: Let \( G \) be an oriented graph represented by the GLOVER structure with minimum degree \( k \). The first container \( C_i \) in which the complete graph \( K_{2i+1} \) (with \( 2i+1 \) nodes) occurs is given by:
\[
i = \frac{k-1}{2}
\]
where \( k \) is the minimum degree of \( G \).
proof: We begin be stating some previously shown examples:
proof: We begin be stating some previously shown examples:
- For \( k = 3 \): \( K_3 \) (triangle) occurs in \( C_1 \).
- For \( k = 5 \): \( K_5 \) occurs in \( C_2 \).
- For \( k = 7 \): \( K_7 \) occurs in \( C_3 \). These observations hold as each container's regularity and density increase due to the degree-doubling properties, allowing the nodes to support the arcs required for the corresponding complete graph. The GLOVER structure ensures that each container \( C_i \) has a regular structure where the degrees of nodes double, leading to increasing density. The size and arc density of \( C_i \) grow as \( i \) increases, providing the necessary structure for complete graphs. The minimum degree \( k \) determines how far from \( v_0 \) (the chosen minimum-degree node) we need to go before the density of a container is sufficient to form \( K_{2i+1} \). The relationship \( i = \frac{k-1}{2} \) arises naturally because \( k \) controls the initial sparsity of \( G \), and the degree-doubling property ensures density increases predictably in the GLOVER structure.
label: Formula for Complete Graph Occurrence
content: Let \( G \) be an oriented graph represented by the GLOVER structure, with minimum degree \( k \), and let the complete graph occur in container \( C_i \). Then every node in container \( C_i \) has its degree doubled in the representation.
proof:
label: Multiple Degree Doubling Nodes
proof:
label: Multiple Degree Doubling Nodes
content: We're going to start selecting the neighborhoods. We know that the first neighborhood is simply the out-neighbors of the minimum out-degree node, so |R_1| = 7.
proof:
label:
proof:
label:
content: We'll talk about neighborhood 1. Nodes need to have degree at least 1. This means that there are at most 6 nodes in neighborhood 2, to keep v0 from having it's degree double.
proof:
label:
proof:
label:
content: Now on to Neighborhood 2. This is the most complicated. in this case we want to show that nodes need to have at least degree 2. So we can show that if any node has degree 1, then it must have 6 exterior neighbors to neighborhood 3. These are second neighbors of the nodes in neighborhood 1. Those nodes already had their interior out-degree double since it's 1. So this makes their exterior out-degree double, causing their overall degree to double. This means that nodes in neighborhood 2 need interior degree 2.
proof:
label:
proof:
label:
content: Continuing with neighborhood 2.
These nodes can have degree at least 2. The mode balanced degree distribution of a complete graph of neighborhood 2 if [3, 3, 3, 2, 2, 2], which will still leave nodes of degree 2. This means that neighborhood 3 must have at least 5 nodes.
proof:
label:
proof:
label:
content: Then we talk about neighborhood 3. We first need to force the nodes in this neighborhood to have degree 3. Similar to previous neighborhoods, we start by supposing a node is degree 2. That means that the node will have exterior degree 5. That exterior degree will be too neighborhood 4. These nodes in neighborhood 4 will be second exterior neighbors of nodes in neighborhood 2, making that second neighborhood
proof:
label:
proof:
label:
content: The thing is, we can't have a graph if 5 nodes with every node of degree 3, by density constraints. 5 choose 2 is 10 and this requires 15 arcs.
proof:
label:
proof:
label:
Note:
We’re continuously improving our visualizations to enhance your experience. Future updates will include additional visualizations, user interactions, and features like force-directed graphs. If you have feedback or suggestions, we’d love to hear from you! Stay tuned for updates.
We’re continuously improving our visualizations to enhance your experience. Future updates will include additional visualizations, user interactions, and features like force-directed graphs. If you have feedback or suggestions, we’d love to hear from you! Stay tuned for updates.