No Arabic abstract
Let $D_{v,b,k}$ denote the family of all connected block designs with $v$ treatments and $b$ blocks of size $k$. Let $dinD_{v,b,k}$. The replication of a treatment is the number of times it appears in the blocks of $d$. The matrix $C(d)=R(d)-frac{1}{k}N(d)N(d)^top$ is called the information matrix of $d$ where $N(d)$ is the incidence matrix of $d$ and $R(d)$ is a diagonal matrix of the replications. Since $d$ is connected, $C(d)$ has $v-1$ nonzero eigenvalues $mu_1(d),...,mu_{v-1}(d)$. Let $D$ be the class of all binary designs of $D_{v,b,k}$. We prove that if there is a design $d^*inD$ such that (i) $C(d^*)$ has three distinct eigenvalues, (ii) $d^*$ minimizes trace of $C(d)^2$ over $dinD$, (iii) $d^*$ maximizes the smallest nonzero eigenvalue and the product of the nonzero eigenvalues of $C(d)$ over $dinD$, then for all $p>0$, $d^*$ minimizes $(sum_{i=1}^{v-1}mu_i(d)^{-p})^{1/p}$ over $dinD$. In the context of optimal design theory, this means that if there is a design $d^*inD$ such that its information matrix has three distinct eigenvalues satisfying the condition (ii) above and that $d^*$ is E- and D-optimal in $D$, then $d^*$ is $Phi_p$-optimal in $D$ for all $p>0$. As an application, we demonstrate the $Phi_p$-optimality of certain group divisible designs. Our proof is based on the method of KKT conditions in nonlinear programming.
We deal with connected $k$-regular multigraphs of order $n$ that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given $k$. For $k=2,3,7$, the Moore graphs are largest. For $k e 2,3,7,57$, we show an upper bound $nleq k^2-k+1$, with equality if and only if there exists a finite projective plane of order $k-1$ that admits a polarity.
In his survey Beyond graph energy: Norms of graphs and matrices (2016), Nikiforov proposed two problems concerning characterizing the graphs that attain equality in a lower bound and in a upper bound for the energy of a graph, respectively. We show that these graphs have at most two nonzero distinct absolute eigenvalues and investigate the proposed problems organizing our study according to the type of spectrum they can have. In most cases all graphs are characterized. Infinite families of graphs are given otherwise. We also show that all graphs satifying the properties required in the problems are integral, except for complete bipartite graphs $K_{p,q}$ and disconnected graphs with a connected component $K_{p,q}$, where $pq$ is not a perfect square.
In this paper we study optimality aspects of a certain type of designs in a multi-way heterogeneity setting. These are ``duals of plans orthogonal through the block factor (POTB). Here by the dual of a main effect plan (say $rho$) we mean a design in a multi-way heterogeneity setting obtained from $rho$ by interchanging the roles of the block factors and the treatment factors. Specifically, we take up two series of universally optimal POTBs for symmetrical experiments constructed in Morgan and Uddin (1996). We show that the duals of these plans, as multi-way designs, satisfy M-optimality. Next, we construct another series of multiway designs and proved their M-optimality, thereby generalising the result of Bagchi and Shah (1989). It may be noted that M-optimality includes all commonly used optimality criteria like A-, D- and E-optimality.
An $(n,r,s)$-system is an $r$-uniform hypergraph on $n$ vertices such that every pair of edges has an intersection of size less than $s$. Using probabilistic arguments, R{o}dl and v{S}iv{n}ajov{a} showed that for all fixed integers $r> s ge 2$, there exists an $(n,r,s)$-system with independence number $Oleft(n^{1-delta+o(1)}right)$ for some optimal constant $delta >0$ only related to $r$ and $s$. We show that for certain pairs $(r,s)$ with $sle r/2$ there exists an explicit construction of an $(n,r,s)$-system with independence number $Oleft(n^{1-epsilon}right)$, where $epsilon > 0$ is an absolute constant only related to $r$ and $s$. Previously this was known only for $s>r/2$ by results of Chattopadhyay and Goodman
A magic labelling of a graph $G$ with magic sum $s$ is a labelling of the edges of $G$ by nonnegative integers such that for each vertex $vin V$, the sum of labels of all edges incident to $v$ is equal to the same number $s$. Stanley gave remarkable results on magic labellings, but the distinct labelling case is much more complicated. We consider the complete construction of all magic labellings of a given graph $G$. The idea is illustrated in detail by dealing with three regular graphs. We give combinatorial proofs. The structure result was used to enumerate the corresponding magic distinct labellings.