OAI/Computability/LoopMatching/SparseBoundary.lean

GitHub source file

8 declarations, 0 contain sorry, 0 declared as axioms

Polynomial-time approximation of weighted matchings with singleton loops.

  1. def OAI.LoopMatching.recordedVertices line 10
  2. theorem OAI.LoopMatching.recordedVertices_card_le line 15
  3. theorem OAI.LoopMatching.ordinary_endpoints_mem_recordedVertices line 22
  4. theorem OAI.LoopMatching.loop_mem_recordedVertices line 43
  5. theorem OAI.LoopMatching.range_subset_recordedVertices_of_weight_ne_zero line 56
  6. theorem OAI.LoopMatching.vertex_bound_of_weight_ne_zero line 80
  7. theorem OAI.LoopMatching.count_eq_zero_of_sparse_bound line 87
  8. theorem OAI.LoopMatching.vertex_bound_of_count_ne_zero line 94