Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralized laminar families and certain forbidden matrices
97
0
0.0
(
0
)
Authors
Peter Dukes
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 permutation 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 show 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 generalized 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
