Circulant almost cross intersecting families

DOI10.26493/2590-9770.1414.F67MaRDI QIDQ5045251zbMATH OpenOpenAlexFDO

Authors Michal Parnas

Publication date 4 November 2022

Published in The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.07907

zbMATH Keywords

Boolean rankcirculant matrixintersecting setsisolation set

Mathematics Subject Classification ID

Extremal set theory (05D05) Boolean and Hadamard matrices (15B34)

Abstract: Let $mathcalF$ and $mathcalG$ be two $t$-uniform families of subsets over $[k]=1,2,\mathrm{...},k$, where $|mathcalF|=|mathcalG|$, and let $C$ be the adjacency matrix of the bipartite graph whose vertices are the subsets in $mathcalF$ and $mathcalG$, and there is an edge between $AinmathcalF$ and $BinmathcalG$ if and only if $AcapBeqemptyset$. The pair $(mathcalF,mathcalG)$ is $q$-almost cross intersecting if every row and column of $C$ has exactly $q$ zeros. We consider $q$-almost cross intersecting pairs that have a circulant intersection matrix $C_{p,q}$, determined by a column vector with $p>0$ ones followed by $q>0$ zeros. This family of matrices includes the identity matrix in one extreme, and the adjacency matrix of the bipartite crown graph in the other extreme. We give constructions of pairs $(mathcalF,mathcalG)$ whose intersection matrix is $C_{p,q}$, for a wide range of values of the parameters $p$ and $q$, and in some cases also prove matching upper bounds. Specifically, we prove results for the following values of the parameters: (1) $1leqpleq2t-1$ and $1leqqleqk-2t+1$. (2) $2tleqpleq{t}^2$ and any $q>0$, where $kgeqp+q$. (3) $p$ that is exponential in $t$, for large enough $k$. Using the first result we show that if $kgeq4t-3$ then $C_{2t-1,k-2t+1}$ is a maximal isolation submatrix of size $kimesk$ in the $0,1$-matrix $A_{k,t}$, whose rows and columns are labeled by all subsets of size $t$ of $[k]$, and there is a one in the entry on row $x$ and column $y$ if and only if subsets $x,y$ intersect.

Recommendations

• Uniformly cross intersecting families
• Intersections and distinct intersections in cross-intersecting families
• On cross t-intersecting families of sets
• Counting intersecting and pairs of cross-intersecting families
• Almost intersecting families

Cites work

• A new generalization of the Erdős-Ko-Rado theorem
• Almost cross-intersecting and almost cross-Sperner pairs of families of sets
• Almost Intersecting Families of Sets
• An extremal problem for two families of sets
• Circulant Boolean relation matrices
• Communication Complexity
• scientific article; zbMATH DE number 3492862 (Why is no real title available?)
• scientific article; zbMATH DE number 3541041 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 1054724 (Why is no real title available?)
• Hypergraphs of Bounded Disjointness
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Intersection patterns of convex sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Isolation number versus Boolean rank
• On circulant Boolean matrices
• On generalized graphs
• On maximal isolation sets in the uniform intersection matrix
• On the complexity of Boolean matrix ranks
• Some best possible inequalities concerning cross-intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The Boolean rank of the uniform intersection matrix and a family of its submatrices
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• The maximum sum and the maximum product of sizes of cross-intersecting families

Cited in

(2)

• Regular intersecting families
• On maximal isolation sets in the uniform intersection matrix

This page was built for publication: Circulant almost cross intersecting families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5045251)