매트로이드 둘레

Matroid girth

수학적 학문인 매트로이드 이론에서 매트로이드의 둘레는 가장 작은 회로나 종속 집합의 크기를 말한다.매트로이드의 톱니바퀴는 이중 매트로이드의 둘레다.Matroid Girth는 그래프에서 가장 짧은 주기의 개념, 그래프의 가장자리 연결, 홀 세트(Hall sets in permitial graph), 짝수 세트(Hall sets) 및 심지어 세트 세트 세트(set of set) 및 포인트 세트의 일반적 위치(general position)를 일반화한다.계산하기는 어렵지만, 선형표현의 영역 크기와 매트로이드 순위에 의해 매개변수화된 경우 선형 매트로이드에 대해 고정 매개변수를 추적할 수 있다.

예

"거스" 용어는 그래프 이론에서 둘레의 사용을 일반화하는데, 이것은 그래프에서 가장 짧은 주기의 길이를 의미한다: 그래픽 매트로이드의 둘레는 그 기본 그래프의 둘레와 같다.[1]

다른 등급의 매트로이드의 둘레도 중요한 결합 문제에 해당된다.예를 들어, 동그래픽 매트로이드의 둘레(또는 그래픽 매트로이드의 톱니바퀴)는 기본 그래프의 가장자리 연결성, 즉 그래프의 최소 절단에 있는 가장자리 수와 동일하다.[1]횡단 매트로이드의 둘레는 초당적 그래프에 설정된 최소 홀의 카디널리티를 제공한다: 이것은 그래프에서 일치의 끝점 집합을 형성하지 않는 초당적 분할의 한 쪽에 있는 정점 집합이다.[2]

유클리드 공간의 모든 점 집합은 점의 데카르트 좌표를 매트로이드 표현 벡터로 해석함으로써 실제 선형 매트로이드에 이르게 한다.결과 매트로이드의 둘레는 기본 점 집합이 일반 위치에 있을 때 공간의 치수를 더한 것과 같으며, 그렇지 않으면 더 작다.실제 선형 매트로이드의 둘레는 압축 감지에서도 발생하며, 여기서 같은 개념을 매트릭스의 스파크라고 한다.[3]

이항 매트로이드의 둘레는 각 세트 요소의 짝수 개수를 포함하는 세트 패밀리의 하위 집합인 짝수 집합의 카디널리티를 제공한다.[2]

계산 복잡성

이항 매트로이드의 둘레를 결정하는 것은 NP-hard이다.[4]

또한 매트로이드를 나타내는 행렬에 의해 주어진 선형 매트로이드의 둘레를 결정하는 것은 둘레 또는 매트로이드의 등급에 의해 매개변수화된 경우 W[1]-강성이지만, 기본 필드의 크기와 순위 조합에 의해 매개변수화된 경우 고정 매개변수를 추적할 수 있다.[2]

독립성 신탁에 의해 주어진 임의의 매트로이드의 경우 하위 수의 매트로이드 쿼리를 사용하여 둘레를 찾을 수 없다.[5]마찬가지로, 요소들의 r투플의 방향을 제시하는 오라클에서 설명하는 n개의 요소를 가진 r등급의 실제 선형 매트로이드의 경우, 둘레를 결정하기 위해서는 ( - ) 개의 오라클 쿼리가 필요하다.[6]

둘레 오라클( 주어진 요소 집합 중 가장 작은 종속 부분 집합을 보고하는 오라클)을 사용한 연산도 고려되었다.[7]

참조

  1. ^ a b Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR 2365057.
  2. ^ a b c Panolan, 파하드, Ramanujan, M.S.;Saurabh, 사켓(2015년),"둘레 및 연결 문제의 매개 변수 복잡성 선형 matroids에"(PDF), Dehne에, 프랭크, 약탈, Jörg-Rüdiger, Stege, Ulrike(eds.), 알고리즘 및 데이터 구조:14일 국제 심포지엄, WADS 2015년, 빅토리아, 캐나다 BC, 8월 5-72015년까지는집, 강의 노트.S컴퓨터 과학으로, 9214, 스프링거,를 대신하여 서명함. 566–577, doi:10.1007/978-3-319-21840-3_47 vol..
  3. ^ Donoho, David L.; Elad, Michael (2003), "Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization", Proceedings of the National Academy of Sciences of the United States of America, 100 (5): 2197–2202, doi:10.1073/pnas.0437847100, PMC 153464, PMID 16576749.
  4. ^ 조, 첸 & 딩(2007)은 이것이 코드 이론에서 알렉산더 바디의 결과의 골수라고 관찰한다.
  5. ^ Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing, 11 (1): 184–190, doi:10.1137/0211014, MR 0646772.
  6. ^ Erickson, J.; Seidel, R. (1995), "Better lower bounds on detecting affine and spherical degeneracies", Discrete and Computational Geometry, 13 (1): 41–57, doi:10.1007/BF02574027, MR 1300508.
  7. ^ Hausmann, D.; Korte, B. (1981), "Algorithmic versus axiomatic definitions of matroids", Mathematical programming at Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979), Mathematical Programming Studies, vol. 14, pp. 98–111, doi:10.1007/BFb0120924, MR 0600125.