| 姓名 |
楊千儒(Chien-Ju Yang)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
0和1構成的飽和矩陣、123-強制矩陣與12..k-置換趨避矩陣
(Saturation, 123-forcing, and 12..k-permutation-avoiding of 0-1 matrices)
|
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
0-1矩陣是僅由0和1為元素構成的矩陣。令A為一個0-1矩陣，若存在任一A的子矩陣，透過將任意數量的元素1轉換成0可以使其與一0-1矩陣P相等，則稱此0-1矩陣A包含0-1矩陣P，且該子矩陣稱為一個P的複製。若0-1矩陣A不包含P，且將任一個元素0轉換成1會使得矩陣A包含P ，那麼我們稱A是一個P的飽和矩陣。取自[1]和[2]的研究結果，我們將介紹有最大和最小數量的1的Ik的飽和矩陣和Jk的飽和矩陣，並將一些證明改的更精簡。
另外，我們還會討論的是強制矩陣和置換趨避矩陣，這兩種都是行數和列數相同
的矩陣。令A為一個n × n的0-1矩陣，若A所包含的每個大小為n × n的置換矩陣皆包
含單位矩陣I3，那麼我們稱A是一個123-強制矩陣。若A所包含的每個n × n的置換矩陣
皆不包含k × k的單位矩陣Ik ，那麼A被稱為一個12 . . . k-置換趨避矩陣。我們會仔細釐
清[3]中對於有最大數量的1的123-強制矩陣的條件。最後，為了解決[1]中的一項未解問
題，對於12 . . . k-置換趨避矩陣，我們猜想在任意n × n的12 . . . k-置換趨避矩陣中，0的最小數量為((n-k+2)¦2)。 |
| 摘要(英) |
A 0-1 matrix consists of entries that are either 0 or 1. A 0-1 matrix A contains a 0-1
matrix P if A has a submatrix that can be made equal to P by changing any number
of 1-entries to 0-entries. This submatrix is called a copy of P in A. A 0-1 matrix A is
saturating for a 0-1 matrix P if A does not contain P, yet turning an arbitrary 0-entry of A into a 1-entry creates a copy of P in A. In the saturation problems, we introduce the results from [1] and [2] concerning the maximum and minimum numbers of 1-entries in matrices saturating for Ik and Jk, and succinctly rephrase some of the proofs. Another line of research focuses on square matrices. An n × n 0-1 matrix A is a 123-forcing matrix if every n × n permutation matrix in A contains the identity matrix I3. Conversely, an n × n 0-1 matrix A is 12..k-permutation-avoiding if none of n × n permutation matrix in A contains the identity matrix Ik. We clarify the characterization of 123-forcing matrices from [3] with the maximum number of 1-entries, and add missing parts to the original proof to make it complete. Finally, we conjecture that the minimum number of 0-entries in any n × n 12 . . . k-permutation-avoiding matrices is ((n-k+2)¦2), aiming to solve an open problem in [1]. |
| 關鍵字(中) |
★ 0-1 矩陣
★ 趨避矩陣
★ 飽和
★ 強制矩陣
★ 置換趨避矩陣 |
關鍵字(英) |
★ 0-1 matrix
★ excluded matrix
★ saturation
★ forcing matrix
★ permutation-avoiding matrix |
| 論文目次 |
XÅ i
Abstract ii
å" iii
1 Introduction 1
2 Saturation matrices 3
2-1 Matrices saturating for Ik . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2-2 Matrices saturating for Jk . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Forcing matrices and permutation-avoiding matrices 27
3-1 123-forcing matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3-2 12 . . . k-permutation-avoiding matrices . . . . . . . . . . . . . . . . . . . . 45
4 Conclusion 52
References 53 |
| 參考文獻 |
[1] Richard A. Brualdi and Lei Cao. Pattern-avoiding (0,1)-matrices and bases of per- mutation matrices. Discrete Appl. Math., 304:196–211, 2021.
[2] Radoslav Fulek and Bal ́azs Keszegh. Saturation problems about forbidden 0-1 sub- matrices. SIAM J. Discrete Math., 35(3):1964–1977, 2021.
[3] Richard A. Brualdi and Lei Cao. 123-forcing matrices. Australas. J. Combin., 86:169– 186, 2023.
[4] Shen-Fu Tsai. Saturation of multidimensional 0-1 matrices. Discrete Math. Lett., 11:91–95, 2023.
[5] Richard A. Brualdi and Lei Cao. Blockers of pattern avoiding permutation matrices. Australas. J. Combin., 83:274–303, 2022. |
| 指導教授 |
蔡昇甫(Shen-Fu Tsai)
|
審核日期 |
2024-7-23 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
