Search

Two $n$-dimensional vectors $A$ and $B$, $A,B \in \mathbb{R}^n$, are said to be \emph{trivially orthogonal} if in every coordinate $i \in [n]$, at least one of $A(i)$ or $B(i)$ is zero. Given the $n$-dimensional Hamming cube $\{0,1\}^n$, we study the minimum cardinality of a set $\mathcal{V}$ of $n$-dimensional $\{-1,0,1\}$ vectors, each containing exactly $d$ non-zero entries, such that every `possible' point $A \in \{0,1\}^n$ in the Hamming cube has some $V \in \mathcal{V}$ which is orthogonal, but not trivially orthogonal, to $A$. We give asymptotically tight lower and (constructive) upper bounds for such a set $\mathcal{V}$ except for the even values of $d \in \Omega(n^{0.5+\epsilon})$, for any $\epsilon$, $0< \epsilon \leq 0.5$., Comment: 9 pages, 1 figure

Let $G(V,E)$ be a $k$-uniform hypergraph. A hyperedge $e \in E$ is said to be properly $(r,p)$ colored by an $r$-coloring of vertices in $V$ if $e$ contains vertices of at least $p$ distinct colors in the $r$-coloring. An $r$-coloring of vertices in $V$ is called a {\it strong $(r,p)$ coloring} if every hyperedge $e \in E$ is properly $(r,p)$ colored by the $r$-coloring. We study the maximum number of hyperedges that can be properly $(r,p)$ colored by a single $r$-coloring and the structures that maximizes number of properly $(r,p)$ colored hyperedges.