Proof of Proposition 3.1, p. 158 — lecture l_a of K_b is at period k iff m_ab has the color of period-node k; colorings of Ĝ ↔ feasible schedules
ProvedTimetabling85.CourseColoring.coloring_interpretationLet be a course scheduling problem with unavailabilities and preassignments (CSUP) in periods, and let be its graph: lecture-nodes , period-nodes , the edges of the lecture graph, all pairs of period-nodes, joined to when course cannot be held at period , and joined to every when has to be held at period .
- For every node colouring of with colours there is a solution of in periods with
- Conversely, for every solution of in periods there is a node colouring of with colours related to in the same way.
This is the interpretation of the coloured graph given in the proof of Proposition 3.1: the schedule is read off a colouring through the colours of the period-nodes.
Formalization Note The colouring's palette is Fin p, but the statement does not require period-node to receive colour : a colouring may permute the colours of the period clique, and the schedule is read through the colour of each period-node.
import Mathlib import Definitions.Def_Timetabling85_CourseColoring_CSUP
namespace Timetabling85.CourseColoring
theorem coloring_interpretation {q r p : ℕ} (P : CSUP q r p) :
(∀ c : P.csupGraph.Coloring (Fin p), ∃ s : P.Lecture → Fin p, P.IsFeasible s ∧
∀ (l : P.Lecture) (k : Fin p), s l = k ↔ c (Sum.inl l) = c (Sum.inr k)) ∧
(∀ s : P.Lecture → Fin p, P.IsFeasible s → ∃ c : P.csupGraph.Coloring (Fin p),
∀ (l : P.Lecture) (k : Fin p), s l = k ↔ c (Sum.inl l) = c (Sum.inr k)) := by sorry
end Timetabling85.CourseColoring
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.