Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMartin Gardners minimum no-3-in-a-line problem
169
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In Martin Gardners October, 1976 Mathematical Games column in Scientific American, he posed the following problem: What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a row, a column, or a diagonal? We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even.
rate research
Read More
Our main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs. We conclude by exploring how some of these results over the finite field of order 2 extend to arbitrary fields and demonstrate that at least one third of the 62 are minimal forbidden subgraphs over an arbitrary field for the class of graphs having minimum rank at most 3 in that field.
A emph{sign pattern (matrix)} is a matrix whose entries are from the set ${+, -, 0}$. The emph{minimum rank} (respectively, emph{rational minimum rank}) of a sign pattern matrix $cal A$ is the minimum of the ranks of the real (respectively, rational) matrices whose entries have signs equal to the corresponding entries of $cal A$. A sign pattern $cal A$ is said to be emph{condensed} if $cal A$ has no zero row or column and no two rows or columns are identical or negatives of each other. In this paper, a new direct connection between condensed $m times n $ sign patterns with minimum rank $r$ and $m$ point--$n$ hyperplane configurations in ${mathbb R}^{r-1}$ is established. In particular, condensed sign patterns with minimum rank 3 are closed related to point--line configurations on the plane. It is proved that for any sign pattern $cal A$ with minimum rank $rgeq 3$, if the number of zero entries on each column of $cal A$ is at most $r-1$, then the rational minimum rank of $cal A$ is also $r$. Furthermore, we construct the smallest known sign pattern whose minimum rank is 3 but whose rational minimum rank is greater than 3.
In the chapter Magic with a Matrix in emph{Hexaflexagons and Other Mathematical
In this paper, we study the rainbow ErdH{o}s-Rothschild problem with respect to 3-term arithmetic progressions. We obtain the asymptotic number of $r$-colorings of $[n]$ without rainbow 3-term arithmetic progressions, and we show that the typical colorings with this property are 2-colorings. We also prove that $[n]$ attains the maximum number of rainbow 3-term arithmetic progression-free $r$-colorings among all subsets of $[n]$. Moreover, the exact number of rainbow 3-term arithmetic progression-free $r$-colorings of $mathbb{Z}_p$ is obtained, where $p$ is any prime and $mathbb{Z}_p$ is the cyclic group of order $p$.
The minimum forcing number of a graph $G$ is the smallest number of edges simultaneously contained in a unique perfect matching of $G$. Zhang, Ye and Shiu cite{HDW} showed that the minimum forcing number of any fullerene graph was bounded below by $3$. However, we find that there exists exactly one excepted fullerene $F_{24}$ with the minimum forcing number $2$. In this paper, we characterize all fullerenes with the minimum forcing number $3$ by a construction approach. This also solves an open problem proposed by Zhang et al. We also find that except for $F_{24}$, all fullerenes with anti-forcing number $4$ have the minimum forcing number $3$. In particular, the nanotube fullerenes of type $(4, 2)$ are such fullerenes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
