포장매트로이드

매트로이드의 수학적 이론에서 포장 매트로이드는 모든 회로가 최소한 매트로이드의 순위만큼의 크기를 갖는 매트로이드를 말한다.계급 r의 matroid에서{r\displaystyle}모든 회로 대부분의 r+1{\displaystyle r+1}, 그래서 그것은 matroids은 모든 회로의 크기는 집합{r, r+1}{\displaystyle\와 같이{r,r+1\}에 속하}포장용 matroids을 정의하는 것과 동일하다 .[1]는 거의 모든 matroids 있포장용 matroid 것으로 추측해 왔다 size다.s

예

3등급의 모든 단순 매트는 포장 매트로이드다. 예를 들어 이것은 Pano 매트로이드에 해당된다.바모스 마트로이드는 4위라는 또 다른 예를 제공한다.

r $순위{\displaystyle }$ r$${\$displaystyle r$}의 균일한 매트로이드는 모든 회로의 길이가 $정확히{\displaystyle }$ ${\displaystyle \mathrm{r}}$+ 1${\displaystyle$ r$+1$}이므로$$ 모두 포장 매트로이드라는 특성을 가지고$$ 있으며,^[2] 예를 들어, 완전한 $그래프{\displaystyle {}_{}}$ ${\displaystyle {K\mathrm{}}_{}}$ 4${\$의 사이클 매트로이 포장으로 되어$$ 있지만 균일하지는 않다.^[3]

A Steiner system ${\displaystyle S(t,k,v)}$ is a pair ${\displaystyle (S,{\mathcal {D}})}$ where ${\displaystyle S}$ is a finite set of size ${\displaystyle v}$ and ${\displaystyle {\mathcal {D}}}$ is a family of ${\displaystyle k}$-element subsets of ${\displaysty$$모든{\displaystyle }$ $t{\displaystyle }$ ${\displaystyle t}$ -element$$ subset of S ${\displaystyle S}$이(가) $D{\displaystyle \mathcal{}}$ ${\$에서 정확히 한 세트씩의 하위 집합인$$ 속성을 가진$$ $le$ S$\}.$$D{\displaystyle \mathcal{}}$ ${\$의 요소는 $S{\displaystyle }$ ${\displaystyle S}$의 $t{\displaystyle }$ ${\displaystyle$ S$}$ -partition을$$ 형성하므로$$$$ $S{\displaystyle }$ ${\displaystyle S}$에 포장 매트로이드의 하이퍼플레인이 된다$.$^[4]

d-파티션

포장 매트로이드의 $순위$가 ${\displaystyle \mathrm{d}}$ +${\displaystyle }$1 ${\displaystyle d+1}$인 경우, $그{\displaystyle }$ $하이퍼플레인$은 d {\displaystyle d$}$ -partition으로$$ 알려진 세트 시스템을 형성한다$.$A family of two or more sets ${\displaystyle {\mathcal {F}}}$ forms a ${\displaystyle d}$-partition if every set in ${\displaystyle {\mathcal {F}}}$ has size at least ${\displaystyle d}$ and every ${\displaystyle d}$-element subset of ${\displaystyle \bigcup {\mathcal {F}}}$ is a subsetof exactly one set in ${\displaystyle {\mathcal {F}}}$. Conversely, if ${\displaystyle {\mathcal {F}}}$ is a ${\displaystyle d}$-partition, then it can be used to define a paving matroid on ${\displaystyle E=\bigcup {\mathcal {F}}}$ for which ${\displaystyle {\mathcal {F}}}$ is the set고플레인의${\displaystyle 이}$ 매트로이드에서 ${\displaystyle E}$ ${\$$displaystyle E}$의 $하위{\displaystyle }$ 집합 I ${\$$displaystyle$I$\leq d}$ ${\displaystyle 또는}$ ${\displaystyle I}$=${\displaystyle 1}$ ${\displaystyle$I$=d+1}$및$$ $I{\displaystyle }$ ${\displaystystyle I}$은(는) $F{\displaystyle \mathcal{}}$ ${\displaystystystyle$ {$F$^[1]에 설정된 하위 집합이 아니다$$$$.

콤비네이터 열거

최대 9개 원소에 대한 단순 매트로이드의 결합체 열거 결과, 이들 중 많은 부분이 또한 포장 매트로이드인 것으로 나타났다.^[1]이를 근거로 거의 모든 모종이 포장된 모종이라고 추측해 왔다.^[5]더 정확히 말하면, 이 추측에 따르면, 포장이 가능한 매트로이드 수와 모든 매트로이드 수의 비율의 한계는 무한대로 가므로 1과 같아야 한다.만일 그렇다면, 희박한 포장 매트리스, 포장 매트리스에 이중인 매트리스에 대해서도 동일한 문구를 만들 수 있다.비록 이것이 여전히 열려있지만, 모종과 희박한 포장 모종 수의 로그의 점근 비율에 대한 유사한 진술이 입증되었다.^[6]

역사

포장용 매트로이드는 초기에 Hartmanis(1959년)에 의해 $d{\displaystyle }$ ${\displaystyle d}$ -partitions의$$ 측면에서 동등한 제형으로 연구되었다. Hartmanis는 이를 일반화된 칸막이 선반이라고 불렀다.1970년 저서 콤비네토리오메트리(Combinatorial Geometries)에서 헨리 슈레토와 지안 카를로 로타는 이 구조물들이 모체(Matroidal)임을 관찰했다; "포장 마트로이드"라는 이름은 로타의 제안으로 웨일스 (1976년)에 의해 소개되었다.^[7]

임의의 모종과 비교하여 포장하는 모종들의 단순한 구조는 모종에 대한 몇몇 사실들이 더 일반적인 경우에서 이해하기 어려운 것으로 증명될 수 있게 했다.그 예로는 Rota의 기초 추측이 있는데, 순위 n 매트로이드에 있는 n개의 불연속 베이스를 n × n 매트릭스로 배열할 수 있다는 진술로, 행렬의 행은 주어진 베이스가 되고 열도 베이스가 된다.그것은 모종을 포장하는 것에 대해 사실인 것으로 증명되었지만, 대부분의 다른 모종에게는 여전히 열려 있다.^[8]

메모들

참조

• Geelen, Jim; Humphries, Peter J. (2006), "Rota's basis conjecture for paving matroids" (PDF), SIAM Journal on Discrete Mathematics, 20 (4): 1042–1045 (electronic), doi:10.1137/060655596, hdl:10092/11877, MR 2272246, archived from the original (PDF) on 2012-06-17, retrieved 2013-02-03.
• Hartmanis, Juris (1959), "Lattice theory of generalized partitions", Canadian Journal of Mathematics, 11: 97–106, doi:10.4153/CJM-1959-013-8, MR 0099931, Zbl 0089.37002.
• Mayhew, Dillon; Newman, Mike; Welsh, Dominic; Whittle, Geoff (2011), "On the asymptotic proportion of connected matroids", European Journal of Combinatorics, 32 (6): 882–890, doi:10.1016/j.ejc.2011.01.016, MR 2821559.
• Oxley, James G. (1992), Matroid theory, Oxford Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5, Zbl 0784.05002
• Pendavingh, Rudi; van der Pol, Jorn (2015), "On the number of matroids compared to the number of sparse paving matroids", The Electronic Journal of Combinatorics, 22 (2), #2.51.
• Welsh, D. J. A. (1976), "2.3. Paving Matroids", Matroid Theory, Courier Dover Publications, pp. 40–41, 44, ISBN 9780486474397. 2010년 재인쇄.