اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGeneralized laminar families and certain forbidden matrices
95
0
0.0
(
0
)
تأليف
Peter Dukes
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Recall that in a laminar family, any two sets are either disjoint or contained one in the other. Here, a parametrized weakening of this condition is introduced. Let us say that a set system $mathcal{F} subseteq 2^X$ is $t$-laminar if $A,B in mathcal{F}$ with $|A cap B| ge t$ implies $A subseteq B$ or $B subseteq A$. We obtain very close asymptotic bounds in terms of $n$ on the maximum size of a $2$-laminar family $mathcal{F} subseteq 2^{[n]}$. A construction for $3$-laminar families and a crude analysis for general $t$ are also given.
قيم البحث
اقرأ أيضاً
A matrix is emph{simple} if it is a (0,1)-matrix and there are no repeated columns. Given a (0,1)-matrix $F$, we say a matrix $A$ has $F$ as a emph{configuration}, denoted $Fprec A$, if there is a submatrix of $A$ which is a row and column permutatio
n of $F$. Let $|A|$ denote the number of columns of $A$. Let $mathcal{F}$ be a family of matrices. We define the extremal function $text{forb}(m, mathcal{F}) = max{|A|colon A text{ is an }m-text{rowed simple matrix and has no configuration } Finmathcal{F}}$. We consider pairs $mathcal{F}={F_1,F_2}$ such that $F_1$ and $F_2$ have no common extremal construction and derive that individually each $text{forb}(m, F_i)$ has greater asymptotic growth than $text{forb}(m, mathcal{F})$, extending research started by Anstee and Koch.
Let $ngeq 3$ and $r_n$ be a $3$-polytopal graph such that for every $3leq ileq n$, $r_n$ has at least one vertex of degree $i$. We find the minimal vertex count for $r_n$. We then describe an algorithm to construct the graphs $r_n$. A dual statement
may be formulated for faces of $3$-polytopes. The ideas behind the algorithm generalise readily to solve related problems. Moreover, given a $3$-polytope $t_l$ comprising a vertex of degree $i$ for all $3leq ileq l$, $l$ fixed, we define an algorithm to output for $n>l$ a $3$-polytope $t_n$ comprising a vertex of degree $i$, for all $3leq ileq n$, and such that the initial $t_l$ is a subgraph of $t_n$. The vertex count of $t_n$ is asymptotically optimal, in the sense that it matches the aforementioned minimal vertex count up to order of magnitude, as $n$ gets large. In fact, we only lose a small quantity on the coefficient of the second highest term, and this quantity may be taken as small as we please, with the tradeoff of first constructing an accordingly large auxiliary graph.
In this paper, we generalize classical constructions of skew Hadamard difference families with two or four blocks in the additive groups of finite fields given by Szekeres (1969, 1971), Whiteman (1971) and Wallis-Whiteman (1972). In particular, we sh
ow that there exists a skew Hadamard difference family with $2^{u-1}$ blocks in the additive group of the finite field of order $q^e$ for any prime power $qequiv 2^u+1,({mathrm{mod, , }2^{u+1}})$ with $uge 2$ and any positive integer $e$. In the aforementioned work of Szekeres, Whiteman, and Wallis-Whiteman, the constructions of skew Hadamard difference families with $2^{u-1}$ ($u=2$ or $3$) blocks in $({mathbb F}_{q^e},+)$ depend on the exponent $e$, with $eequiv 1,2,$ or $3,({mathrm{mod, , }4})$ when $u=2$, and $eequiv 1,({mathrm{mod, , }2})$ when $u=3$, respectively. Our more general construction, in particular, removes the dependence on $e$. As a consequence, we obtain new infinite families of skew Hadamard matrices.
In this paper, we find regular or biregular Hadamard matrices with maximum excess by negating some rows and columns of known Hadamard matrices obtained from quadratic residues of finite fields. In particular, we show that if either $4m^2+4m+3$ or $2m
^2+2m+1$ is a prime power, then there exists a biregular Hadamard matrix of order $n=4(m^2+m+1)$ with maximum excess. Furthermore, we give a sufficient condition for Hadamard matrices obtained from quadratic residues being transformed to be regular in terms of four-class translation association schemes on finite fields.
We propose a quantum walk defined by digraphs (mixed graphs). This is like Grover walk that is perturbed by a certain complex-valued function defined by digraphs. The discriminant of this quantum walk is a matrix that is a certain normalization of ge
neralized Hermitian adjacency matrices. Furthermore, we give definitions of the positive and negative supports of the transfer matrix, and clarify explicit formulas of their supports of the square. In addition, we give tables by computer on the identification of digraphs by their eigenvalues.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
