Back to Search Start Over

Bisecting and D-secting families for set systems

Authors :
Balachandran, Niranjan
Mathew, Rogers
Mishra, Tapas Kumar
Pal, Sudebkumar Prasant
Publication Year :
2016

Abstract

Let $n$ be any positive integer and $\mathcal{F}$ be a family of subsets of $[n]$. A family $\mathcal{F}'$ is said to be $D$-\emph{secting} for $\mathcal{F}$ if for every $A \in \mathcal{F}$, there exists a subset $A' \in \mathcal{F}'$ such that $|A \cap A'| - |A \cap ([n] \setminus A')|=i$, where $i \in D$, $D \subseteq \{-n,-n+1,\ldots,0,\ldots,n\}$. A $D$-\emph{secting} family $\mathcal{F}'$ of $\mathcal{F}$, where $D=\{-1,0,1\}$, is a \emph{bisecting} family ensuring the existence of a subset $A' \in \mathcal{F}'$ such that $|A \cap A'| \in \{\lceil \frac{|A|}{2}\rceil,\lfloor \frac{|A|}{2}\rfloor\}$, for each $A \in \mathcal{F}$. In this paper, we study $D$-secting families for $\mathcal{F}$ with restrictions on $D$, and the cardinalities of $\mathcal{F}$ and the subsets of $\mathcal{F}$.<br />Comment: 15 pages, text overlap with https://www.ams.org/journals/tran/1987-300-01/S0002-9947-1987-0871675-6/S0002-9947-1987-0871675-6.pdf in Theorem 7

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1604.01482
Document Type :
Working Paper