System of unbiased representatives for a collection of bicolorings

DOI10.1016/J.DAM.2019.03.021MaRDI QIDQ2201776zbMATH OpenOpenAlexFDO

Authors Niranjan Balachandran, Rogers Mathew, Sudebkumar Prasant Pal, Tapas Kumar Mishra

Publication date 17 September 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coveringtest coverHamming cubeseparating familiesbisecting familieshypergraph bicoloring

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Let $mathcalB$ denote a set of bicolorings of $[n]$, where each bicoloring is a mapping of the points in $[n]$ to $-1,+1$. For each $BinmathcalB$, let $Y_B=(B(1),ldots,B(n))$. For each $Asubseteq[n]$, let $X_{A}in{0,1}^n$ denote the incidence vector of $A$. A non-empty set $A$ is said to be an `unbiased representative' for a bicoloring $BinmathcalB$ if $leftlangle{X}_A,Y_{B}ightangle=0$. Given a set $mathcalB$ of bicolorings, we study the minimum cardinality of a family $mathcalA$ consisting of subsets of $[n]$ such that every bicoloring in $mathcalB$ has an unbiased representative in $mathcalA$.

Recommendations

• Geometric systems of unbiased representatives
• Bicoloring Steiner triple systems
• Imbalances in k‐colorations
• Simultaneous Systems of Representatives for Families of Finite Sets
• Balanced two-colorings of finite sets in the cube

Cites work

• scientific article; zbMATH DE number 3161569 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1947395 (Why is no real title available?)
• scientific article; zbMATH DE number 1875415 (Why is no real title available?)
• scientific article; zbMATH DE number 3431965 (Why is no real title available?)
• A 1-matching blossom-type algorithm for edge covering problems
• Almost tight bounds for \(\epsilon\)-nets
• Analytical approach to parallel repetition
• Codes with given distances
• Combinatorial Nullstellensatz
• Covering the cube by affine hyperplanes
• ECONOMICAL COVERS WITH GEOMETRIC APPLICATIONS
• Essential covers of the cube by hyperplanes
• Essential positive covers of the cube
• Extremal combinatorics. With applications in computer science
• Forbidden Intersections
• Frankl-Rödl-type theorems for codes and permutations
• Identification Keys and Diagnostic Tables: A Review
• Minimal completely separating systems
• Minimum Covers of Fixed Cardinality in Weighted Graphs
• On a packing and covering problem
• On a problem concerning separating systems of a finite set
• On separating systems of a finite set
• On separating systems whose elements are sets of at most k elements
• On the intersections of polynomials and the Cayley-Bacharach theorem
• On the ratio of optimal integral and fractional covers
• Parameterized study of the test cover problem
• Partially polynomial kernels for set cover and test cover
• Statistical Properties of Error Estimators in Performance Assessment of Recognition Systems
• The probabilistic method
• Two combinatorial covering theorems
• \(\epsilon\)-nets and simplex range queries

Cited in

(1)

• Geometric systems of unbiased representatives

This page was built for publication: System of unbiased representatives for a collection of bicolorings

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