2
$\begingroup$

According to this paper,a family of intervals is said to be canonical if the coordinates of the endpoints of the intervals are distinct integers between 1 and 2n where n is the number of intervals.

Here is the example Original intervals = {[2,5], [3,11], [6,9], [7,13], [8,18], [12,16], [15,19]}

Canonical form of intervals = {[1,3], [2,8], [4,7], [5,10], [6,13], [9,12], [11,14]}

These original intervals and canonical form of the original intervals give the same interval graph, but how can I prove that it is always the case mathematically ?

Edit: This is the method I use to create canonical intervals: I sort the intervals according to their starting points in ascending order Then, I assign the first interval's [2,5] starting point as 1. Then, I compare it with the following intervals to see the overlappings. Then, I arrange the intervals accordingly.

I repeat this process for all intervals.

Examples:

[2,5] contains only the starting point of interval 2, so

[2,5] becomes [1, (start of interval 2), 3] = [1,3]

[3,11] contains, start of interval 3, start of interval 4, end of interval 3, and start of interval 5, so

[3,11] becomes [2, 3, (start of interval 3), (start of interval 4), (end of interval 3),(start of interval 5),8] = [2,8]

note: interval 2 can not start here because at point 3 because it is where interval 1 ends. All start and end points should be distinct.

$\endgroup$
  • $\begingroup$ The usual way to show something like this is to show that each individual step you perform in changing the original set of intervals into the final set does not change the corresponding interval graph. Then clearly any finite number of steps-that-don't-change-the-interval-graph will not change the interval graph. $\endgroup$ – j_random_hacker Oct 25 '17 at 6:38
1
$\begingroup$

You haven't described how a system of intervals are converted to canonical form, but here is one way to do it. We find an order-preserving mapping (satisfies $f(x) < f(y)$ iff $x < y$) from the coordinates in the original system to the integers $\{1,\ldots,2n\}$ (we do this by sorting all of the original coordinates). We get the same interval graph since the mapping is order-preserving – that's a nice exercise.

$\endgroup$
  • $\begingroup$ Thanks. I edited my question and tried to explain my method to create canonical intervals. $\endgroup$ – eds Aug 25 '17 at 18:57
  • $\begingroup$ Your description is very vague. Before we can prove that an algorithm works, we need to know the algorithm. $\endgroup$ – Yuval Filmus Aug 25 '17 at 19:25
  • $\begingroup$ In any case, this kind of ongoing discussion isn't really suitable for this forum. I suggest contacting a TA. $\endgroup$ – Yuval Filmus Aug 25 '17 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.