Two remarks on eventown and oddtown problems

DOI10.1137/16M1100666zbMATH Open1379.05116arXiv1610.07907OpenAlexW2545227308MaRDI QIDQ4602856FDOQ4602856

Authors:

Publication date: 7 February 2018

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

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$.

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

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

zbMATH Keywords

defectmultiple intersectionseventownoddtown

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hadamard matrices and their applications
• Boolean designs and self-dual matroids
• On Subsets with Intersections of Even Cardinality
• On subsets with cardinalities of intersections divisible by a fixed integer
• Title not available (Why is that?)
• Extremal set systems with weakly restricted intersections
• On the existence of Hadamard matrices
• Exact \(k\)-wise intersection theorems
• Extremal systems with upper-bounded odd intersections

Cited In (2)

• A short note on supersaturation for oddtown and eventown
• Lovász theta approach to eventown problem

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)