메술람의 경기

그래프 이론에서 메술람의 게임은 그래프의 독립 콤플렉스의 동질적 연결성과 관련된 로이 메술람의^[1] 정리를 설명하는 데 사용되는 게임으로, k까지 및 k를 포함한 모든 감소된 동질적 집단이 사소한 것일 정도로 가장 작은 지수 k이다.이 정리가 게임으로 공식화된 것은 아하로니, 버거, 지브 때문이다.^[2]^[3]

설명

게임판은 G 그래프 입니다.CON과 NON이라는 두 플레이어를 위한 제로섬 게임이다.CON은 G의 독립 콤플렉스인 I(G)의 연결성이 높다는 것을 보여주고, NON은 그 반대임을 증명하고자 한다.

그의 차례가 되면 CON은 남은 그래프에서 엣지 e를 선택한다.그런 다음 NON은 다음 두 가지 옵션 중 하나를 선택하십시오.

분리 – 그래프에서 에지 e를 제거하십시오.
폭발 – e의 양쪽 끝점과 모든 이웃 및 가장자리를 제거하십시오.

CON 점수는 다음과 같이 정의된다.

어느 시점에서 나머지 그래프가 분리된 정점을 갖는 경우 점수는 무한하다.
그렇지 않으면, 어떤 시점에서 나머지 그래프에는 꼭지점이 없다. 이 경우 점수는 폭발 수입니다.

주어진 그래프 G마다 G의 게임 값(즉, 양쪽이 최적으로 플레이할 때의 CON 점수)은 ψ(G)로 표시된다.

게임 가치 및 동질적 연결성

Meshulam은^[1] 모든 그래프 G:

$\eta _{H}(I(G)\geq \PSI(G)$

$I(G)$ 서 $\eta _{H}(I(G))$ $\eta _{H}(I(G))$ ( $\eta _{H}(I(G))$ ( $\eta _{H}(I(G))$ ) ${\displaystyle \eta _{H}(I(G)})$ 는 I $I(G)$ ( $I(G)$ ) ${\displaystyle I(G)}+$ 2의 $I(G)$ 동질적 연결이다 $\eta _{H}(I(G))$ .

예

G가 빈 그래프인 경우 폭발이 필요하지 않으므로 ψ(G) = 0이다.
G가 k개의 연결된 구성요소를 가지고 있다면, ((G) k k. CON이 에지를 제공하는 순서와 관계없이, NON에 의해 만들어진 각각의 폭발은 단일 구성요소의 정점을 파괴하므로, NON은 모든 정점을 파괴하기 위해 적어도 k개의 폭발이 필요하다.
G가 k 꼭지점-분리형 집단의 조합인 경우, 각각 최소 두 개의 꼭지점을 포함하는 ((G) = k, 각 폭발은 하나의 집단을 완전히 파괴하기 때문이다.
G의 독립성 지배 번호가 k 이상인 경우, i $i\gamma (G)\geq k$ ( G $i\gamma (G)\geq k$ ) $i\gamma (G)\geq k$ $i\gamma (G)\geq k$ ${\displaystyle$ i $\gamma (G)\geq$ k $},$ $\Psi (G)\geq k$ ( $\Psi (G)\geq k$ ) $\Psi (G)\geq k$ $\Psi (G)\geq k$ \ k $\\displaysty \PSI (G)\geq$ k $\Psi (G)\geq k$ 증명:A가 적어도 K를 지배하는 번호를 가진 독립된 집합이 되게 하라. CON은 A가 A에 있는 모든 에지(a,b)를 제공하는 것으로 시작한다.NON이 그러한 모든 에지를 분리하는 경우, A의 정점은 고립된 상태로 유지되므로 CON의 점수는 무한이다.NON이 그러한 가장자리를 폭발시키면, 그 폭발은 A로부터 b에 인접한 정점만 제거한다(A에서의 폭발은 A의 정점을 파괴하지 않는다, 독립된 집합이기 때문이다).따라서 A의 나머지 정점은 적어도 k-1 정점을 지배해야 하므로 A의 지배 횟수는 최대 1회까지 감소하였다.따라서 NON은 A의 모든 정점을 파괴하기 위해 적어도 k개의 폭발이 필요하다.이것은 $\Psi (G)\geq i\gamma (G)$ ( G $\Psi (G)\geq i\gamma (G)$ ) $\Psi (G)\geq i\gamma (G)$ $\Psi (G)\geq i\gamma (G)$ $\Psi (G)\geq i\gamma (G)$ ( $\Psi (G)\geq i\gamma (G)$ G $\Psi (G)\geq i\gamma (G)$ ) $\displaystyle \Psi (G)\geq$ i\ $gamma (G)}$ 를 증명한다 $\Psi (G)\geq i\gamma (G)$
- Note: this also implies that $\Psi (L(G))\geq \nu (G)/2$ , where $L(G)$ is the line graph of G, and $\nu (G)$ is the size of the largest matching in G.G의 매치들이 L(G)의 독립 세트이기 때문이다.G의 각 에지는 L(G)의 정점이며, 일치에서 최대 두 에지(독립 집합의 정점=)를 지배한다.^[3]
- 마찬가지로 H가 r-partite 하이퍼그래프일 때 when ( $\Psi (L(H))\geq \nu (H)/r$ ( $\Psi (L(H))\geq \nu (H)/r$ ) $\Psi (L(H))\geq \nu (H)/r$ ( $\Psi (L(H))\geq \nu (H)/r$ ) $\Psi (L(H))\geq \nu (H)/r$ / r $\PSI (L(H)\geq \nu (H)/r$ ^[4].
If G is the complete bipartite graphK_n,n, and L(G) is its line graph, then $\Psi (L(G))\geq \lfloor 2n/3\rfloor$ .^[5]^[6]Proof: L(G) can be seen as an n-by-n array of cells, where each row is a vertex on one side, each column is a vertex on the other side, and each cell is an edge.그래프 L(G)에서 각 셀은 꼭지점이며, 각 가장자리는 같은 열 또는 같은 행에 있는 두 셀의 쌍이다.CON은 같은 열에 두 개의 셀을 제공하는 것으로 시작한다. NON이 셀을 폭발시키면 CON은 같은 열에 두 개의 셀을 제공하고, NON이 다시 셀을 폭발시키면 두 개의 폭발이 함께 3줄과 3개의 열을 파괴한다.따라서 모든 정점을 제거하려면 최소한 $\lfloor 2n/3\rfloor$ $2n$ / $\lfloor 2n/3\rfloor$ $\lfloor 2n/3\rfloor$ ${\displaystyle \lfloor$ 2n/ $3\rfloor }$ 폭발이 $\lfloor 2n/3\rfloor$ 필요하다.
- 참고: 이 결과는 나중에 일반화되었다: $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ 가 K의_n,n 하위 그래프라면 $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ ^[3]^{: Thm.3.10} $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ ( $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ ( G $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ ) $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ ≥ $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ - n $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ - 1 $\Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}$ ${\$ {3 $}-{\frac{1}{1$ }2 $}}.$

사례 1에 대한 증거

To illustrate the connection between Meshulam's game and connectivity, we prove it in the special case in which $\eta _{H}(I(G))=1$ , which is the smallest possible value of $\eta _{H}(I(G))$ . We prove that, in this case, ${\displaystyle \Psi (G)$ $\leq 1$ 즉 NON은 항상 최대 한 번의 폭발을 사용하여 전체 그래프를 파괴할 수 있다.

$\eta _{H}(I(G))=1$ $\eta _{H}(I(G))=1$ ( $\eta _{H}(I(G))=1$ ( G $\eta _{H}(I(G))=1$ ) $\eta _{H}(I(G))=1$ = $\eta _{H}(I(G))=1$ $\eta _{H}(I(G)=1$ 은(는) $I(G)$ ( $I(G)$ ) $I(G)$ 이(가) 연결되지 $I(G)$ 않았음을 의미한다 $\eta _{H}(I(G))=1$ .즉, 정점의 두 부분 집합인 X와 Y가 있다는 것을 의미하며, $I(G)$ 서 I $I(G)$ ( $I(G)$ ) ${\displaystyle$ I $(G)}$ 에 에지가 없으면 X의 어떤 정점도 Y의 어떤 정점에 연결되지 $I(G)$ 않는다.그러나 $I(G)$ ( $I(G)$ ) $I(G)$ 은 $I(G)$ G의 독립 콤플렉스여서 G에서는 X의 모든 꼭지점이 Y의 모든 꼭지점에 연결되어 있다. CON이 어떻게 작동하든 그는 어느 단계에서 X의 꼭지점과 Y의 꼭지점 사이의 가장자리를 선택해야 한다. NON은 이 가장자리를 폭발시켜 전체 그래프를 파괴할 수 있다.

일반적으로 증명서는 오직 한 가지 방법, 즉 $\eta _{H}(I(G))>\Psi (G)$ H $\eta _{H}(I(G))>\Psi (G)$ ( $\eta _{H}(I(G))>\Psi (G)$ ( $\eta _{H}(I(G))>\Psi (G)$ ) $\eta _{H}(I(G))>\Psi (G)$ > $\eta _{H}(I(G))>\Psi (G)$ ( $\eta _{H}(I(G))>\Psi (G)$ ) ${\displaystyle \eta _{H(G)}}\PSI (G$ 에 대한 그래프가 있을 수 있다.

참고 항목

하이퍼그래프를 위한 홀형 정리

참조

^ ^a ^b Meshulam, Roy (2003-05-01). "Domination numbers and homology". Journal of Combinatorial Theory, Series A. 102 (2): 321–330. doi:10.1016/S0097-3165(03)00045-1. ISSN 0097-3165.
^ Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 0209-9683. S2CID 43510417.
^ ^a ^b ^c Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 0025-5858. S2CID 119139740.
^ Haxell, Penny; Narins, Lothar; Szabó, Tibor (2018-08-01). "Extremal hypergraphs for Ryser's Conjecture". Journal of Combinatorial Theory, Series A. 158: 492–547. doi:10.1016/j.jcta.2018.04.004. ISSN 0097-3165.
^ Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994). "Chessboard Complexes and Matching Complexes". Journal of the London Mathematical Society. 49 (1): 25–39. doi:10.1112/jlms/49.1.25. ISSN 1469-7750.
^ Shareshian, John; Wachs, Michelle L. (2009-10-01). "Top homology of hypergraph matching complexes, p-cycle complexes and Quillen complexes of symmetric groups". Journal of Algebra. 322 (7): 2253–2271. arXiv:0808.3114. doi:10.1016/j.jalgebra.2008.11.042. ISSN 0021-8693. S2CID 5259429.

[:0-1] Meshulam, Roy (2003-05-01). "Domination numbers and homology". Journal of Combinatorial Theory, Series A. 102 (2): 321–330. doi:10.1016/S0097-3165(03)00045-1. ISSN 0097-3165.

[2] Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 0209-9683. S2CID 43510417.

[:1-3] Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 0025-5858. S2CID 119139740.

[4] Haxell, Penny; Narins, Lothar; Szabó, Tibor (2018-08-01). "Extremal hypergraphs for Ryser's Conjecture". Journal of Combinatorial Theory, Series A. 158: 492–547. doi:10.1016/j.jcta.2018.04.004. ISSN 0097-3165.

[5] Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994). "Chessboard Complexes and Matching Complexes". Journal of the London Mathematical Society. 49 (1): 25–39. doi:10.1112/jlms/49.1.25. ISSN 1469-7750.

[6] Shareshian, John; Wachs, Michelle L. (2009-10-01). "Top homology of hypergraph matching complexes, p-cycle complexes and Quillen complexes of symmetric groups". Journal of Algebra. 322 (7): 2253–2271. arXiv:0808.3114. doi:10.1016/j.jalgebra.2008.11.042. ISSN 0021-8693. S2CID 5259429.

[1]

[2]

[3]

[4]

[5]

[6]

Search

메술람의 경기

네임스페이스

더

목차

설명

게임 가치 및 동질적 연결성

예

사례 1에 대한 증거

참고 항목

참조