D-간격 하이퍼그래프

그래프 이론에서 d-간격 하이퍼그래프는 실제 선의 간격을 이용하여 구성된 하이퍼그래프의 일종이다.매개변수 d는 양의 정수다.d-간격 하이퍼그래프의 정점은 d 분리 선의 지점이다(정점 수가 셀 수 없이 많다).그래프의 가장자리는 간격의 d-touple로, 모든 실제 선에 하나의 구간이다.^[1]

가장 간단한 경우는 d = 1이다.1간 하이퍼그래프의 꼭지점 집합은 실제 숫자의 집합이다. 그러한 하이퍼그래프의 각 가장자리는 실제 선의 간격이다.예를 들어 집합 {-2, -1], [0, 5], [3, 7] }은(는) 1간 하이퍼그래프를 정의한다.구간 그래프와의 차이에 유의하십시오. 구간 그래프에서 정점은 구간(한정된 집합)이며, 1-간격 하이퍼그래프에서는 정점이 모두 실제 선의 점(할 수 없는 집합)이다.

또 다른 예로, 2간 하이퍼그래프에서 정점 집합은 두 개의 실제 선의 분리 결합이며, 각 가장자리는 두 개의 간격의 결합이다: 1번 선과 2번 선이다.

다음 두 가지 개념은 유한 하이퍼그래프와 마찬가지로 d-간격 하이퍼그래프에 대해 정의된다.

• 일치는 비절연 에지 집합, 즉 비절연 d-절연 집합이다.예를 들어, 1간 하이퍼그래프 {-2, -1], [0, 5], [3, 7] }, 집합 {-2, -1], [0, 5] }은(는) 크기 2의 일치가 되지만 집합 {0,5, 5], [3,7] }은(는) 요소들이 교차하기 때문에 일치가 아니다.H에서 가장 큰 일치 크기는 $\nu {\displaystyle }$( ${\displaystyle H}$) ${\displaystyle \nu (H)}$로 표시된다$.$
• 덮개 또는 횡단(transversal)은 모든 가장자리와 교차하는 정점 집합, 즉 모든 d-간격과 교차하는 점 집합이다.예를 들어 1간 하이퍼그래프 {-2, -1, [0, 5], [3, 7] }에서 집합 {-1.5, 4 }은(는) 크기 2의 덮개지만 집합 {-1.5, 1}은 가장자리[3,7]와 교차하지 않으므로 덮개가 아니다.H에서 가장 작은 횡단 크기는 $\tau {\displaystyle }$( ${\displaystyle H}$) ${\displaystyle \tau (H)}$로 표시된다$.$

${\displaystyle \nu }$( ${\displaystyle H}$) ${\displaystyle \le }$( ${\displaystyle H}$ )$displaystyle \nu (H)\leq \tau ($H)}은$($는) 모든 하이퍼그래프 H에 대해 참이다.

티보르 갈라이는 1간격 하이퍼그래프에서 그것들이 동일하다는 것을 증명했다: $\nu {\displaystyle }$(${\displaystyle }$H${\displaystyle }$) = ${\displaystyle (}$ (${\displaystyle H}$ ) = ${\displaystyle \tau }$ (${\displaystyle H)}$ $\displaystyle \nu (H)=\tau (H)}.$ 이것은 Kőnig의 초당적 그래프의 정리와 유사하다$.$

가보르 타도스는^[1] 2간 하이퍼그래프에서 $\tau {\displaystyle }$(${\displaystyle H}$ ${\displaystyle )}$ ${\displaystyle \le }$ ( H )$≤$ ${\displaystyle 2}$ ${\displaystyle \nu }$ ( ${\displaystyle H}$) \$displaystyle \tau$ ($H)\leq$ 2\nu $(H)}$가$$빠듯하며, (즉, 크기가 일치하는 모든 2간 하이퍼그래프는 2m 포인트로 커버할 수 있다는 것을 증명했다.

Kaiser^[2] proved that, in a d-interval hypergraph, ${\displaystyle \tau (H)\leq d(d-1)\nu (H)}$, and moreover, every d-interval hypergraph with a matching of size m, can be covered by at d(d − 1)m points, (d − 1)m points on each line.

프릭과 제르비브는^[3] 이 정리의 다채로운 ("레인보우") 버전을 증명했다.

참조