Two remarks on eventown and oddtown problems

DOI10.1137/16M1100666MaRDI QIDQ4602856zbMATH OpenOpenAlexFDO

Authors

Publication date 7 February 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

defecteventownmultiple intersectionsoddtown

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal set theory (05D05) Algebraic combinatorics (05E99)

Abstract: A family $mathcalA$ of subsets of an $n$-element set is called an eventown (resp. oddtown) if all its sets have even (resp. odd) size and all pairwise intersections have even size. Using tools from linear algebra, it was shown by Berlekamp and Graver that the maximum size of an eventown is $2^{leftlfloorn/2ightfloor}$. On the other hand (somewhat surprisingly), it was proven by Berlekamp, that oddtowns have size at most $n$. Over the last four decades, many extensions of this even/oddtown problem have been studied. In this paper we present new results on two such extensions. First, extending a result of Vu, we show that a $k$-wise eventown (i.e., intersections of $k$ sets are even) has for $kgeq3$ a unique extremal configuration and obtain a stability result for this problem. Next we improve some known bounds for the defect version of an $ell$-oddtown problem. In this problem we consider sets of size $otequiv0pmodell$ where $ell$ is a prime number $ell$ (not necessarily $2$) and allow a few pairwise intersections to also have size $otequiv0pmodell$.

Recommendations

• A short note on supersaturation for oddtown and eventown
• A note on k-wise oddtown problems
• Extremal systems with upper-bounded odd intersections
• Specified intersections
• Uniform eventown problems

Cites work

• Boolean designs and self-dual matroids
• Exact \(k\)-wise intersection theorems
• Extremal set systems with weakly restricted intersections
• Extremal systems with upper-bounded odd intersections
• Graph theory
• Hadamard matrices and their applications
• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 3732068 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• On subsets with cardinalities of intersections divisible by a fixed integer
• On Subsets with Intersections of Even Cardinality
• On the existence of Hadamard matrices

Cited in

(8)

• Lovász theta approach to eventown problem
• A note on k-wise oddtown problems
• Uniform eventown problems
• A short note on supersaturation for oddtown and eventown
• Kneser's theorem for codes and -divisible set families
• On supersaturation for oddtown and eventown
• On set systems with strongly restricted intersections
• q-analogues of Fisher's inequality and oddtown theorem

This page was built for publication: Two remarks on eventown and oddtown problems

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