Linear discrepacy of partially ordered sets
- 발행기관 서강대학교 대학원
- 지도교수 이재권
- 발행년도 2007
- 학위수여년월 200702
- 학위명 박사
- 학과 및 전공 수학
- 식별자(기타) 000000103793
- 본문언어 영어
초록/요약
In this thesis, we determine the linear discrepancy of the product of three chains of each size $n$ and construct optimal isotones corresponding to them. Also, we characterize posets of linear discrepancy 2 by the irreducibility with respect to the linear discrepancy. We first investigate some properties for the linear discrepancy, and give some examples reflecting the properties investigated. From these and the arithmetic-geometry inequality, we determine that the linear discrepancy of the product of three chains of each size 2n is 6n^3-2n^2-1. Next, we give an upper bound and a lower bound of the linear discrepancy of the product of three chains of each size 2n+1. Finally, we define the irreducibility with respect to the linear discrepancy and find all 1-, 2-irreducible posets and some 3-irreducible posets. Using these, we characterize posets of the linear discrepancy 1 and those of the linear discrepancy 2 and width 2.
more초록/요약
본 논문은 사슬의 곱으로 이루어진 순서집합의 선형상위도(線型相違度, linear discrepancy)를 결정하는 문제와 그 선형상위도를 가지는 최적 순서보존함수를 구현하는 문제를 다루었으며, 또한 선형상위도에서의 기약성을 이용하여 선형상위도가 2인 순서집합을 특성화하였다. 우선, 선형상위도에 대한 성질을 파악하여 임의의 크기의 두 개의 사슬의 곱에 대한 선형상위도를 결정하였다. 그리고 산술평균 기하평균의 부등식을 이용하여 크기가 2n인 사슬 세 개의 곱의 선형상위도가 6n^3-2n^2-1임을 계산하였고, 크기가 2n+1인 사슬 세 개의 곱의 선형상위도에 대한 상계과 하계를 구하고 가설을 제시하였다. 다음으로, 선형상위도에서의 기약성을 정의하고, 선형상위도가 1, 2이면서 기약인 순서집합과 선형상위도가 3이면서 그 폭이 2이고 기약인 순서집합을 모두 찾았다. 이를 이용하여, 선형상위도가 1인 순서집합과 선형상위도가 2이면서 폭이 2인 순서집합의 특성을 묘사하였다.
more