Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower bounds on maximal determinants of binary matrices via the probabilistic method
94
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $D(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and ${mathcal R}(n) = D(n)/n^{n/2}$ be the ratio of $D(n)$ to the Hadamard upper bound. We give several new lower bounds on ${mathcal R}(n)$ in terms of $d$, where $n = h+d$, $h$ is the order of a Hadamard matrix, and $h$ is maximal subject to $h le n$. A relatively simple bound is [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2} left(1 - d^2left(frac{pi}{2h}right)^{1/2}right) ;text{ for all }; n ge 1.] An asymptotically sharper bound is [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2} expleft(dleft(frac{pi}{2h}right)^{1/2} + ; Oleft(frac{d^{5/3}}{h^{2/3}}right)right).] We also show that [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2}] if $n ge n_0$ and $n_0$ is sufficiently large, the threshold $n_0$ being independent of $d$, or for all $nge 1$ if $0 le d le 3$ (which would follow from the Hadamard conjecture). The proofs depend on the probabilistic method, and generalise previous results that were restricted to the cases $d=0$ and $d=1$.
rate research
Read More
Let ${mathcal D}(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and $mathcal R(n) = {mathcal D}(n)/n^{n/2}$ be the ratio of ${mathcal D}(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on ${mathcal D}(n)$ and $mathcal R(n)$ in terms of $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h le n$. For example, $mathcal R(n) > (pi e/2)^{-d/2}$ if $1 le d le 3$, and $mathcal R(n) > (pi e/2)^{-d/2}(1 - d^2(pi/(2h))^{1/2})$ if $d > 3$. By a recent result of Livinskyi, $d^2/h^{1/2} to 0$ as $n to infty$, so the second bound is close to $(pi e/2)^{-d/2}$ for large $n$. Previous lower bounds tended to zero as $n to infty$ with $d$ fixed, except in the cases $d in {0,1}$. For $d ge 2$, our bounds are better for all sufficiently large $n$. If the Hadamard conjecture is true, then $d le 3$, so the first bound above shows that $mathcal R(n)$ is bounded below by a positive constant $(pi e/2)^{-3/2} > 0.1133$.
We give upper and lower bounds on the determinant of a perturbation of the identity matrix or, more generally, a perturbation of a nonsingular diagonal matrix. The matrices considered are, in general, diagonally dominant. The lower bounds are best possible, and in several cases they are stronger than well-known bounds due to Ostrowski and other authors. If $A = I-E$ is an $n times n$ matrix and the elements of $E$ are bounded in absolute value by $varepsilon le 1/n$, then a lower bound of Ostrowski (1938) is $det(A) ge 1-nvarepsilon$. We show that if, in addition, the diagonal elements of $E$ are zero, then a best-possible lower bound is [det(A) ge (1-(n-1)varepsilon),(1+varepsilon)^{n-1}.] Corresponding upper bounds are respectively [det(A) le (1 + 2varepsilon + nvarepsilon^2)^{n/2}] and [det(A) le (1 + (n-1)varepsilon^2)^{n/2}.] The first upper bound is stronger than Ostrowskis bound (for $varepsilon < 1/n$) $det(A) le (1 - nvarepsilon)^{-1}$. The second upper bound generalises Hadamards inequality, which is the case $varepsilon = 1$. A necessary and sufficient condition for our upper bounds to be best possible for matrices of order $n$ and all positive $varepsilon$ is the existence of a skew-Hadamard matrix of order $n$.
Given positive integers $p$ and $q$, a $(p,q)$-coloring of the complete graph $K_n$ is an edge-coloring in which every $p$-clique receives at least $q$ colors. ErdH{o}s and Shelah posed the question of determining $f(n,p,q)$, the minimum number of colors needed for a $(p,q)$-coloring of $K_n$. In this paper, we expand on the color energy technique introduced by Pohoata and Sheffer to prove new lower bounds on this function, making explicit the connection between bounds on extremal numbers and $f(n,p,q)$. Using results on the extremal numbers of subdivided complete graphs, theta graphs, and subdivided complete bipartite graphs, we generalize results of Fish, Pohoata, and Sheffer, giving the first nontrivial lower bounds on $f(n,p,q)$ for some pairs $(p,q)$ and improving previous lower bounds for other pairs.
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in $O(Delta + log^* n)$ communication rounds; here $n$ is the number of nodes and $Delta$ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on $n$ is optimal: these problems cannot be solved in $o(log^* n)$ rounds even if $Delta = 2$. However, the dependency on $Delta$ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in $o(Delta + log log n / log log log n)$ rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in $o(Delta + log n / log log n)$ rounds; this is an improvement over prior lower bounds also as a function of $n$.
The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. By Mincs conjecture, there exists a reachable upper bound on the permanent of 2-dimensional (0,1)-matrices. In this paper we obtain some generalizations of Mincs conjecture to the multidimensional case. For this purpose we prove and compare several bounds on the permanent of multidimensional (0,1)-matrices. Most estimates can be used for matrices with nonnegative bounded entries.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
