0和1構成的飽和矩陣、123-強制矩陣與12..k-置換趨避矩陣;Saturation, 123-forcing, and 12..k-permutation-avoiding of 0-1 matrices

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/95746

Title:	0和1構成的飽和矩陣、123-強制矩陣與12..k-置換趨避矩陣;Saturation, 123-forcing, and 12..k-permutation-avoiding of 0-1 matrices
Authors:	楊千儒;Yang, Chien-Ju
Contributors:	數學系
Keywords:	0-1 矩陣;趨避矩陣;飽和;強制矩陣;置換趨避矩陣;0-1 matrix;excluded matrix;saturation;forcing matrix;permutation-avoiding matrix
Date:	2024-07-23
Issue Date:	2024-10-09 17:14:23 (UTC+8)
Publisher:	國立中央大學
Abstract:	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].
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	27	View/Open

社群 sharing

Loading...