簡易檢索 / 詳目顯示
| 研究生： |
王昕芸 Wang, Sin-Yun |
|---|---|
| 論文名稱： |
Exact hyperplane covers for subsets of bricks Exact hyperplane covers for subsets of bricks |
| 指導教授： |
林延輯
Lin, Yen-Chi |
| 口試委員： |
林延輯
Lin, Yen-Chi 俞韋亘 Yu, Wei-Hsuan 戴尚年 Shagnik Das |
| 口試日期： | 2023/06/28 |
| 學位類別： |
碩士 Master |
| 系所名稱： |
數學系 Department of Mathematics |
| 論文出版年： | 2024 |
| 畢業學年度： | 112 |
| 語文別： | 英文 |
| 論文頁數： | 28 |
| 英文關鍵詞： | hypercube, bricks, hyperplanes, exact covers |
| DOI URL： | http://doi.org/10.6345/NTNU202400601 |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：93 下載：2 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
Let h_1, h_2, ..., h_n be n positive integers, and V=V(h_1, h_2, ..., h_n) be a set of lattice points (y_1, y_2, ..., y_n) such that 0≤ y_i≤ h_i. Given S⊆V=V(h_1, h_2, ..., h_n), the exact cover of VS is a collection of hyperplanes whose union intersects V(h_1, h_2, ..., h_n) exactly in VS. That is, the points from S are not covered. The exact cover number of VS, denoted by ec(VS), is the minimum size of an exact cover of VS. Alon and Füredi (1993) proved that ec({0, 1}^n{0})=n and if S⊆V=V(h_1, h_2, ..., h_n) with |S|=1, then ec(VS)= Σ(from i=1 to n)h_i. Aaronson et al. (2021) showed that if |S|=2, 3, then ec({0, 1}^nS)=n-1. If |S|=4, then ec({0, 1}^nS)=n-1 if there is a hyperplane Q with |Q∩S|=3, and ec({0, 1}^nS)=n-2 otherwise.
In this paper, we combine the problems mentioned above, and study the problem of covering V(h_1, h_2, ..., h_n) while missing two, three, or four points. Let S be a subset of V=V(h_1, h_2, ..., h_n) with |S|=2,3,4. Our main results are as follows. If |S|=2, then ec(VS)= Σ(from i=1 to n)h_i-1. If |S|=3 and the dimension n=2, then ec(VS)=h_1+h_2-2 if the three points in S are coaxial, and ec(VS)=h_1+h_2-1 otherwise. If |S|=3 and the three points in S are not collinear, then ec(VS)= Σ(from i=1 to n)h_i-1. If |S|=3 and the three points in S are coaxial, then ec(VS)= Σ(from i=1 to n)h_i-2. For the case of missing three collinear points and missing four points, we have partial results. Some cases have matching upper and lower bounds, but some still have gaps.
J. Aaronson, C. Groenland, A. Grzesik, T. Johnston, and B. Kielak. Exact hyperplane covers for subsets of the hypercube. Discrete Mathematics, 344(9):112490, 2021.
N. Alon and Z. Füredi. Covering the cube by affine hyperplanes. European Journal of Combinatorics, 14(2):79–83, 1993.
M. ApS. The MOSEK optimization toolbox for MATLAB manual. Version 10.0.34., 2023.
S. Ball and O. Serra. Punctured combinatorial Nullstellensätze. Combinatorica, 29(5):511–522, 2009.
A. Bishnoi, S. Boyadzhiyska, S. Das, and T. Mészáros. Subspace coverings with multiplicities. arXiv preprint arXiv:2101.11947, 2021.
A. Clifton and H. Huang. On almost k-covers of hypercubes. Combinatorica, 40(4):511– 526, 2020.
A. Ghosh, C. Kayal, and S. Nandi. An optimal generalization of Alon and Füredi’s cov ering result. arXiv preprint arXiv:2207.13752, 2022.
M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, ver sion 2.2. http://cvxr.com/cvx, Mar. 2014.
T. M. Inc. Matlab version: 9.13.0 (r2022b), 2022.
W. A. Stein et al. Sage Mathematics Software (Version 9.3). The Sage Development Team, 2021. http://www.sagemath.org.
