finite_vertex_set_edge_encoding
def
The non-diagonal unordered vertex pairs spanned by a finite vertex set.
Statement
def finite_vertex_set_edge_encoding {V : Type*} [DecidableEq V] (s : Finset V) : Finset (Sym2 V)
- Source
- Bridge from vertex-triangle packings to point-set families for the separator route.
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 36
- simple_graph_triangle_packing_support_unmarked_edge_internalLet U be the edge support of a maximal triangle packing on a vertex set S, and let M contain each support edge that is the only support…
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- simple_graph_maximum_packing_fixed_two_budget_counterexampleA nine-vertex graph has a maximum triangle packing with at most one singleton-forced edge per packed triangle, but no triangle cover…
- simple_graph_edge_reduction_inequalityLet G be a finite simple graph. Suppose there exist a nonempty edge set F ⊆ E(G), a set S of pairwise edge-disjoint triangles of G, and an…
- finite_packing_k4_old_edges_avoidFor an edge-disjoint family containing abc whose union avoids the three spokes from x, removing abc leaves a family whose encoded edges…
- simple_graph_two_edge_stable_connected_family_exchange_trap_counterexampleThere is a connected 18-vertex graph with 57 edges, packing number 14, all edge pairs avoidable by maximum packings, at least three…
- simple_graph_triangle_edge_family_memA set of three edges belongs to the triangle edge family of G iff it is the set of non-diagonal pairs spanned by some three vertices…
- simple_graph_triangle_packing_number_ge_of_edge_reductionLet G be a finite simple graph, F a nonempty edge subset, S a pairwise edge-disjoint triangle family, and X an edge subset such that X…
- simple_graph_unrestricted_singleton_witness_edge_union_counterexampleThe unrestricted witness-edge union does not satisfy the proposed sunflower forced-base half-independence statement: the explicitly…
- finite_vertex_family_edge_packing_cover_bridgeEncoding each member of a finite vertex-set family of size at least two by its non-diagonal pairs preserves the family size, converts…
- simple_graph_stable_disjoint_edges_outside_packing_incompatible_exampleThere is a stable graph of triangle packing number three, a maximum packing P, and a five-edge triangle cover containing two…
- simple_graph_stable_lex_private_triangle_direct_exchange_counterexampleThere is a stable graph with a unique minimum triangle edge cover and a maximum packing such that the cover has exactly one edge outside…
- simple_graph_triangle_cover_of_unique_triangle_edgeIf an edge belongs to exactly one triangle, then the triangle cover-packing inequality for the graph obtained by deleting the other two…
- ten_vertex_exchange_family_eqThe 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
- simple_graph_sunflower_packing_witnessA witness vertex for a packed petal q: a vertex x outside q such that q \ {r} together with x is a triangle meeting the packed edge union…
- simple_graph_pair_stable_private_k4_packing_incidenceLet a maximum packing in a two-edge-stable graph contain abc, with a and b private to that packing triangle. If abcx is a four-clique…
- simple_graph_maximum_packing_private_k4_edge_codegree_twoIf a triangle in a maximum edge-disjoint triangle packing has two vertices private to that triangle and extends to a four-clique whose…
- simple_graph_sunflower_packing_kernel_graphThe kernel graph H: every edge of G with both endpoints in the union of the petals of Q, plus, for each petal q of Q, the two edges that…
- simple_graph_stable_two_packing_arbitrary_cover_counterexampleThere is a finite edge-deletion-stable graph with triangle packing number two, a maximum packing P, and a four-edge triangle cover C such…
- simple_graph_stable_lex_outside_forces_triangle_exampleThere is an edge-stable eight-vertex graph and maximum triangle packing P such that every minimum triangle cover minimizing its outside-P…
- simple_graph_triangle_cover_number_le_of_edge_reductionLet G be a finite simple graph, F a nonempty edge subset, S a pairwise edge-disjoint triangle family, and X an edge subset such that X…
- simple_graph_lex_cover_private_triangle_not_extendable_exampleThere is a stable graph with triangle packing number two, a maximum packing P, and a minimum triangle cover C minimizing its edges outside…
- simple_graph_pair_stable_support_max_incidence_two_bad_packing_counterexampleThere is an eight-vertex two-edge-stable graph with a maximum triangle packing covering every vertex, in which every vertex belongs to at…
- finite_vertex_set_edge_encoding_disjoint_iff_inter_card_le_oneTwo finite vertex sets have disjoint non-diagonal unordered-pair encodings exactly when their intersection contains at most one vertex.
- simple_graph_stable_unforced_anchor_ten_exampleA two-edge-stable graph has a full-support maximum packing with a fully forced K4 face whose internal anchor lies only in unforced packed…
- finite_vertex_set_edge_encoding_mapEncoding non-diagonal vertex pairs commutes with injective relabeling.
- simple_graph_triangle_edge_family_induce_mapThe image of the triangle edge-family of an induced graph is exactly the original graph triangle edge-family restricted to triangles…
- simple_graph_in693_ten_seed_packing_numberThe concrete ten-vertex five-link seed has triangle packing number eight.
- simple_graph_triangle_packing_support_four_k_vertex_kernelLet P be an edge-disjoint triangle family whose edge union meets every graph triangle. If each packed triangle has at most one singly…
- simple_graph_forced_k4_face_pivot_retains_forcingIf an edge-disjoint triangle packing contains abc and a four-clique abcx has no packed spokes ax, bx, cx, replacing abc by abx preserves…
- simple_graph_stable_min_two_triangles_conflict_five_cycleThere is an 11-vertex graph with a maximum packing of five edge-disjoint triangles, every graph edge omitted by some maximum packing and…
- simple_graph_maximum_packing_two_forced_edges_k4For a maximum triangle packing, if a packed triangle has two singleton-forced edges then its three vertices have a common fourth vertex…
- simple_graph_maximal_packing_single_forced_edge_support_counterexampleA graph has a maximal edge-disjoint packing P of five triangles with at most one singly forced edge on each packed triangle, but no…
- simple_graph_stable_packing_twelve_seed_supergraph_rigidityFor the displayed 20-vertex, 60-edge seed, any supergraph on the same vertices in which every edge lies in at least two triangles and…
- simple_graph_stable_triangle_active_edge_in_maximum_packingIn a finite graph where deleting any edge preserves the maximum triangle packing number, every edge belonging to a triangle is used by…
- simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartiteThere is a triangle-active two-edge-stable eight-vertex graph with a support-maximal maximum triangle packing in which every vertex is in…
Lean source view module on GitHub
def finite_vertex_set_edge_encoding {V : Type*} [DecidableEq V] (s : Finset V) : Finset (Sym2 V) := s.sym2.filter (fun e => ¬ e.IsDiag)