System of unbiased representatives for a collection of bicolorings

DOI10.1016/J.DAM.2019.03.021zbMATH Open1448.05200arXiv1704.07716OpenAlexW2964228896MaRDI QIDQ2201776FDOQ2201776

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

Publication date: 17 September 2020

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Forbidden Intersections
• On a packing and covering problem
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• On the ratio of optimal integral and fractional covers
• Parameterized Study of the Test Cover Problem
• The probabilistic method
• Combinatorial Nullstellensatz
• Extremal Combinatorics
• Analytical approach to parallel repetition
• On a problem concerning separating systems of a finite set
• Statistical Properties of Error Estimators in Performance Assessment of Recognition Systems
• A 1-matching blossom-type algorithm for edge covering problems
• Minimum Covers of Fixed Cardinality in Weighted Graphs
• Covering the cube by affine hyperplanes
• Minimal completely separating systems
• Essential covers of the cube by hyperplanes
• Essential positive covers of the cube
• 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
• Codes with given distances
• Two combinatorial covering theorems
• Frankl-Rödl-type theorems for codes and permutations
• Partially Polynomial Kernels for Set Cover and Test Cover
• Identification Keys and Diagnostic Tables: A Review
• ECONOMICAL COVERS WITH GEOMETRIC APPLICATIONS

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)