اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTable of minimum ranks of graphs of order at most 7 and selected optimal matrices
189
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i eq j$) is nonzero whenever ${i,j}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. We have also established several additional strategies for computation of minimum rank. These techniques have been used to determine the minimum ranks of all graphs of order 7. This paper contains a list of minimum ranks for all graphs of order at most 7. We also present selected optimal matrices.
قيم البحث
اقرأ أيضاً
If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $pm1$, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable. In this arti
cle, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$, $K_{n/2,n/2}$, $2K_{n/2}$, and $nK_1$, and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to order 36. Note that it is not even known how many Hadamard matrices there are of order 36.
Let $n geq r geq s geq 0$ be integers and $mathcal{F}$ a family of $r$-subsets of $[n]$. Let $W_{r,s}^{mathcal{F}}$ be the higher inclusion matrix of the subsets in ${mathcal F}$ vs. the $s$-subsets of $[n]$. When $mathcal{F}$ consists of all $r$-sub
sets of $[n]$, we shall simply write $W_{r,s}$ in place of $W_{r,s}^{mathcal{F}}$. In this paper we prove that the rank of the higher inclusion matrix $W_{r,s}$ over an arbitrary field $K$ is resilient. That is, if the size of $mathcal{F}$ is close to ${n choose r}$ then $mbox{rank}_{K}(W_{r,s}^{mathcal{F}}) = mbox{rank}_{K}(W_{r,s})$, where $K$ is an arbitrary field. Furthermore, we prove that the rank (over a field $K$) of the higher inclusion matrix of $r$-subspaces vs. $s$-subspaces of an $n$-dimensional vector space over $mathbb{F}_q$ is also resilient if ${rm char}(K)$ is coprime to $q$.
Let $G$ be an $n$-vertex graph with the maximum degree $Delta$ and the minimum degree $delta$. We give algorithms with complexity $O(1.3158^{n-0.7~Delta(G)})$ and $O(1.32^{n-0.73~Delta(G)})$ that determines if $G$ is 3-colorable, when $delta(G)geq 8$ and $delta(G)geq 7$, respectively.
A {it sign pattern matrix} is a matrix whose entries are from the set ${+,-, 0}$. The minimum rank of a sign pattern matrix $A$ is the minimum of the ranks of the real matrices whose entries have signs equal to the corresponding entries of $A$. It is
shown in this paper that for any $m times n$ sign pattern $A$ with minimum rank $n-2$, rational realization of the minimum rank is possible. This is done using a new approach involving sign vectors and duality. It is shown that for each integer $ngeq 9$, there exists a nonnegative integer $m$ such that there exists an $ntimes m$ sign pattern matrix with minimum rank $n-3$ for which rational realization is not possible. A characterization of $mtimes n$ sign patterns $A$ with minimum rank $n-1$ is given (which solves an open problem in Brualdi et al. cite{Bru10}), along with a more general description of sign patterns with minimum rank $r$, in terms of sign vectors of certain subspaces. A number of results on the maximum and minimum numbers of sign vectors of $k$-dimensional subspaces of $mathbb R^n$ are obtained. In particular, it is shown that the maximum number of sign vectors of $2$-dimensional subspaces of $mathbb R^n$ is $4n+1$. Several related open problems are stated along the way.
What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turan, Rademacher solved the first non-trivial case of this problem in 1941. The problem was revived by ErdH{o}s in 1955; it is now
known as the ErdH{o}s-Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from~$1$, which in this range confirms a conjecture of Lovasz and Simonovits from 1975. Furthermore, we give a description of the extremal graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
