Abstract
A cover-free family is a family of subsets of a finite set in which no one is covered by the union of r others. We study a variation of cover-free family: A binary matrix is (r, w]-consecutive-disjunct if for any w cyclically consecutive columns
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\textbf{\textit{C}}_\textbf{\textit{1}} , \cdots , \textbf{\textit{C}}_\textbf{\textit{w}}$$
\end{document}
and another r cyclically consecutive columns
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\textbf{\textit{C}}_\textbf{\textit{w + 1}} , \cdots , \textbf{\textit{C}}_\textbf{\textit{w + r}}$$
\end{document}
, there exists one row intersecting
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\textbf{\textit{C}}_\textbf{\textit{1}} , \cdots , \textbf{\textit{C}}_\textbf{\textit{w}}$$
\end{document}
but none of
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\textbf{\textit{C}}_\textbf{\textit{w}} + \textbf{\textit{1}} , \cdots , \textbf{\textit{C}}_\textbf{\textit{w}} + \textbf{\textit{r}}$$
\end{document}
. In group testing, the goal is to determine a small subset of positive items D in a large population
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal N}$$
\end{document}
by group tests. By applying consecutive-disjunct matrices, we solve threshold group testing of consecutive positives in
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${\bf 15} {\bf log}_{\bf 2} \frac{\textbf{\textit{n}}}{\textbf{\textit{d}}} + {\bf 4d} + {\bf 71}$$
\end{document}
group tests nonadaptively, and the decoding complexity is
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\textbf{\textit{O}} \left(\frac{\textbf{\textit{n}}}{\textbf{\textit{d}}} \, {\bf log}_{\bf
2} \frac{\textbf{\textit{n}}}{\textbf{\textit{d}}} +
\textbf{\textit{u}} \textbf{\textit{d}}^{\bf 2}\right)$$
\end{document}
where u is a threshold parameter in threshold group testing and it is assumed that |D|≤d and
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mid { \cal N} \mid = \textbf{\textit{n}}$$
\end{document}
. Meanwhile, we obtain that for group testing of consecutive positives, all positives can be identified in
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ {\bf 5} \, {\bf log}_{\bf 2}
\frac{\textbf{\textit{n}}}{\textbf{\textit{d}}} + \textbf{
\textit{2d}} {\bf + 21}$$
\end{document}
group tests nonadaptively and the decoding complexity is
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\textbf{\textit{O}} \left(\frac{\textbf{\textit{n}}}{\textbf{\textit{d}}} \, {\bf log}_{\bf 2} \frac{\textbf{\textit{n}}}{\textbf{\textit{d}}}
+ \textbf{\textit{d}}^{\bf 2}\right)$$
\end{document}
.
