arxiv: 2605.12634 · v1 · submitted 2026-05-12 · 🧮 math.CO

Recognition: unknown

Cover-free families on graphs

Prangya Parida , Lucia Moura

Authors on Pith no claims yet

Pith reviewed 2026-05-14 20:25 UTC · model grok-4.3

classification 🧮 math.CO

keywords cover-free familiesSperner familiesgraph coloringextremal set theorycombinatorial constructionspaths and cyclesmixed-radix representations

0 comments

The pith

For any simple graph G, the minimum t for a G-Sperner family equals t(1, χ(G)).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper generalizes Sperner families and cover-free families by tying the non-containment conditions to the edges of an arbitrary graph G whose vertices stand for the sets. It proves that the resulting parameter t_s(G) is exactly equal to the classical Sperner number t(1, χ(G)). This reduces the problem of finding the smallest ground set that respects a given pattern of incomparabilities to the chromatic number of G. A reader would care because the result supplies an exact answer for the relaxed Sperner condition whenever the chromatic number is known, and it yields new constructive upper bounds for paths, cycles, and several other infinite families.

Core claim

The paper establishes that t_s(G) = t(1, χ(G)) for every simple graph G, where a G-Sperner(t, n) family is a collection of n subsets of a t-element ground set such that, for each edge uv of G, the two corresponding sets are incomparable under inclusion. For the stronger G-CFF parameter t(G) the authors prove the trivial sandwich t(1, n) ≤ t(G) ≤ t(2, n) whenever G has no isolated vertices, show that the lower bound is tight for all stars and the upper bound is tight for complete graphs, and supply explicit constructions that improve the upper bound for paths, cycles, wheels, and windmill graphs, including the bound log₂(n) ≤ t(P_n) ≤ t(C_n) ≤ 1.893 log₂(n) + O(1).

What carries the argument

The G-Sperner family, which enforces set incomparability exactly on the pairs given by the edges of G.

If this is right

The trivial bound t(1, n) ≤ t(G) ≤ t(2, n) holds for every simple graph with no isolated vertex.
The lower bound is tight for every star graph.
The upper bound is tight for every complete graph.
Improved explicit upper bounds exist for paths, cycles, wheels, and windmill graphs via mixed-radix encodings.
Paths and cycles satisfy log₂(n) ≤ t(P_n) ≤ t(C_n) ≤ 1.893 log₂(n) + O(1).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The equality lets any known upper bound on chromatic number immediately supply an upper bound on the size of the corresponding set family.
The mixed-radix Gray-code constructions may extend to other sparse graphs or to d-cover-free families for d > 2.
Graphs with large chromatic number force t(G) closer to the classical t(2, n) than to t(1, n).
The same encoding technique could be tested on random graphs to estimate the typical gap between t(G) and t(1, n).

Load-bearing premise

That any proper coloring of G can be turned into a family of sets on a ground set of size t(1, χ(G)) without creating extra containments.

What would settle it

An explicit graph G together with a family size n for which every collection of n subsets on a ground set of size t(1, χ(G)) violates at least one edge condition of G.

Figures

Figures reproduced from arXiv: 2605.12634 by Lucia Moura, Prangya Parida.

**Figure 1.** Figure 1: t(L12) = t(1, 12) = 6, 6 ≤ t(C12) ≤ 7, and t(K12) = t(2, 12) = 9 isolated vertex and |V (G)| = n ≥ 3. We denote by Sn the star graph with n vertices (see Definition 5.1), by En with n even, the graph with n 2 single edge components (see Notation 5.7), and by G + {x} the graph G with the addition of a universal vertex x (see Notation 4.14). Lower bound for t(G) Extra assumptions for G The lower bound is tig… view at source ↗

**Figure 2.** Figure 2: Sperner graph of order 3 Proof. By definition of S(z), only Sperner families on [1, z] correspond precisely to the cliques in S(z). Hence, by Sperner’s theorem, ω(S(z)) = z ⌊ z 2 ⌋ . Clearly, χ(S(z)) ≥ ω(S(z)) = z ⌊ z 2 ⌋ . It is also well-known from Dilworth’s theorem [3] that the poset of subsets of [1, z] ordered by inclusion can be decomposed into z ⌊ z 2 ⌋ disjoint chains such that each of the c… view at source ↗

**Figure 3.** Figure 3: A P4-disjunct matrix We denote by te(G) and t(G) the minimum t such that there exist a G-ECFF(t, n) and a G-CFF(t, n); respectively: te(G) = min{t : ∃ a G-ECFF(t, |V (G)|)}, t(G) = min{t : ∃ a G-CFF(t, |V (G)|)}. The following proposition is obtained directly from Definition 4.1, by observing that we can vertically concatenate a G-disjunct matrix and a G-Sperner matrix to obtain a G-disjunct matrix. Propos… view at source ↗

**Figure 4.** Figure 4: A k-vertex coloring construction of G-CFF (2) t(Cn) ≤    3 if n = 3, 2t(1, n 2 ) if n is even, n ≥ 4, 2t(1, n 2 ) + 1 if n is odd, n ≥ 5. (3) t(Kn1,n2 ) ≤ t(1, n1) + t(1, n2). (4) t(Tn) ≤ t(1, n1) + t(1, n2) where n1 and n2 are the number of vertices in each of the two color classes for a 2-coloring of Tn. Proof. The result follows from Theorem 4.5 and the fact that Pn, Tn are 2-colorable and Cn i… view at source ↗

**Figure 5.** Figure 5: An optimal S9-disjunct matrix The next corollary provides an infinite family of star graphs Sn such that t(Sn) = t(1, n), showing that the lower bound in Equation 4 is tight [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗

**Figure 6.** Figure 6: C8-CFF(6, 8) constructed from a binary reflected Gray code of length 3 (left) and the corresponding 6 × 8 C8-disjunct matrix (right) The ability to construct Cn-CFFs out of Gray codes ultimately leads us to the problem of how a set of size t should be partitioned into distinct parts such that the product n of the sizes of the parts is maximum. This is a well-studied problem, which has been addressed in com… view at source ↗

**Figure 7.** Figure 7: Examples of a C36-CFF and a C54-CFF [1, 9] = {1, 2, 3} ∪ { ˙ 4, 5, 6} ∪ { ˙ 7, 8, 9}. (a) A P27-CFF(9, 27) built on [1, 9] using R (3,3,3) 3 (b) A C27-CFF(9, 27) and a P27- CFF(9, 27) built on [1, 9] using M3 3 [PITH_FULL_IMAGE:figures/full_fig_p023_7.png] view at source ↗

**Figure 8.** Figure 8: Examples of a P27-CFF and a C27-CFF We further show that the array produced in Construction 6.7 is also a CFF on a generalized Hamming graph defined below. Definition 6.15. A Hamming graph H(d, n) is obtained by the Cartesian product of d complete graphs Kn. A hypercube graph Qd is a Hamming graph H(d, 2). The generalized Hamming graph Ha1,a2,...,ad is the graph Ka1□Ka2□ · · · □Kad . Let H = Ka1□Ka2□ · · ·… view at source ↗

**Figure 9.** Figure 9: A C27-CFF(9, 27) and a C19-CFF(9, 19) for some i ∈ [1, d], xi ̸= yi with {xi , yi} ∈ E(Kai ) and for each j ∈ [1, d] \ {i}, xj = yj . In other words, Ka1□Ka2□ · · · □Kad has the vertex set consisting of codewords of G (a1,a2,...,ad) d and {(x1, x2, . . . , xd),(y1, y2, . . . , yd)} ∈ E(Ka1□Ka2□ · · · □Kad ) if and only if the Hamming distance between (x1, x2, . . . , xd) and (y1, y2, . . . , yd) is 1. Prop… view at source ↗

**Figure 10.** Figure 10: Examples of a friendship graph and a windmill graph Below we give a construction for a Wd(k, n)-disjunct matrix. Construction 7.3. Let Wd(k, n) be a windmill graph with k ≥ 3 and n ≥ 2. Let v0 be the universal vertex and for 1 ≤ i ≤ n, let the vertices of the i th subgraph Kk−1 be vi,1, vi,2, . . . , vi,k−1. Let A be a t(1, n) × n 1-disjunct matrix and let M be a t(2, k − 1) × (k − 1) 2-disjunct matrix, i… view at source ↗

**Figure 11.** Figure 11: A Wd(k, n)-disjunct [PITH_FULL_IMAGE:figures/full_fig_p026_11.png] view at source ↗

**Figure 12.** Figure 12: Types of pair (Bu, Bv) with {u, v} ∈ E(H) as described in Remark 8.2 Lemma 8.3. Let F = (X , B) be a Pn-CFF with |X | = 4 and n ≥ 3. Then n ≤ 4. Proof. Let X = {1, 2, 3, 4} and let V (Pn) = {vi : i ∈ [1, n]} and E(Pn) = {{vi , vi+1} : 1 ≤ i ≤ n − 1}. We split the proof into the following three cases: Case 1 B has a set B with |B| = 3. Without loss of generality, let B = {1, 2, 3} and let vi be the vertex … view at source ↗

**Figure 13.** Figure 13: a. Similarly, if Bv2 = {1, 2, 3}, following the same argument, we conclude that there exists a row r with A[r, v2] = 0 and A[r, v1] = 1, as well as, exactly one row r ′ with A[r ′ , v1] = 0, A[r ′ , v2] = 0, and A[r ′ , l] = 1 for all l ∈ {v3, v4, v5, v6, v7}; see Figure 13b. Now in both cases, consider the submatrix A′ obtained by restricting A to the columns Av3 , Av4 , Av5 , Av6 , and Av7 and to the ro… view at source ↗

**Figure 14.** Figure 14: Case 2.2 of Lemma 8.4 Case 2.3 Let Bv4 = {1, 2, 3}. Since {v3, v4} ∈ E(P7), there exist a row r ∈ {4, 5} with A[r, v4] = 0 and A[r, v3] = 1, and a row r ′ ∈ {4, 5}\{r} with A[r ′ , v3] = 0, A[r ′ , v4] = 0, and A[r ′ , l] = 1 for all l ∈ {v1, v2, v5, v6, v7} (notice the red entries in [PITH_FULL_IMAGE:figures/full_fig_p030_14.png] view at source ↗

**Figure 15.** Figure 15: Case 2.3 of Lemma 8.4 [PITH_FULL_IMAGE:figures/full_fig_p030_15.png] view at source ↗

**Figure 16.** Figure 16: Type of the three subsets removed from 1-CFF(5, 10) as discussed in Case 4 of Lemma 8.4 [PITH_FULL_IMAGE:figures/full_fig_p031_16.png] view at source ↗

**Figure 17.** Figure 17: Maximal graph H in Case 4.4 of Lemma 8.4 any B ∈ B \ {Bv1 }, if Bv2 = B; then it is easy to see that there exists B′ ∈ B such that B′ ⊆ Bv1 ∪ Bv2 , which is a contradiction by Remark 8.2. Thus, n ≤ 6. Case 4.2 Without loss of generality, the subsets removed are {1, 2}, {2, 3}, and {1, 3}. The remaining subsets are {1, 4}, {1, 5}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, and {4, 5}. Let Bv1 = {4, 5}. For any B ∈ B… view at source ↗

read the original abstract

A family of subsets of a $t$-set is a \emph{$d$-cover-free family} or $d$-CFF if no subset in the family is contained in the union of any $d$ other subsets. Let $t(d, n)$ denote the minimum $t$ for which there exists a $d$-CFF on a $t$-set with $n$ subsets. Since a $1$-CFF is the same as a Sperner family, using Sperner's theorem, we get $t(1, n) \sim \log_{2}(n)$ as $n$ grows. Erd\"os, Frankl, and F\"uredi (JCTA, 1982) proved that $3.106\log_{2}(n) < t(2,n) < 5.512\log_{2}(n)$. This paper focuses on generalizing $1$-CFF and $2$-CFF using a graph $G$ where vertices correspond to subsets in the set system. A $G$-Sperner$(t, n)$ is a family of subsets of a $t$-set such that each edge of $G$ specifies a pair of subsets not contained in each other, where as a $G$-CFF$(t, n)$ is a family of subsets of a $t$-set such that it is $G$-Sperner and the union of a pair of subsets corresponding to each edge of $G$ does not contain any other subset in the family. Let $t_s(G)$ and $t(G)$ denote the minimum $t$ for which there exist a $G$-Sperner$(t, n)$ and a $G$-CFF$(t, n)$, respectively. In this way, $t_s(K_n) = t(1, n)$ and $t(K_n) = t(2, n)$. Firstly, we prove $t_s(G) = t(1, \chi(G))$ for any simple graph $G$ and provide various upper and lower bounds for $t(G)$. The \emph{trivial bound}, $t(1, n) \leq t(G) \leq t(2, n)$ holds for any simple graph $G$ with no isolated vertex, with the lower bound tight for an infinite family of star graphs and the upper bound tight for complete graphs. We study when these bounds can be improved and give better constructive upper bounds for families of graphs such as stars, paths, cycles, wheels, and windmill graphs. In particular, a construction based on mixed-radix Gray codes yields $\log_{2}(n) \leq t(P_n) \leq t(C_n) \leq 1.893\log_{2}(n) + \mathcal{O}(1)$ where $P_n$ and $C_n$ are paths and cycles with $n$ vertices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives an exact link from G-Sperner size to chromatic number and improves the upper bound for paths and cycles via Gray-code constructions.

read the letter

The main result is that t_s(G) equals t(1, χ(G)) for any simple graph G. This follows from viewing the G-Sperner condition as a homomorphism into the incomparability graph of the boolean lattice and applying Dilworth plus standard coloring facts. The argument is direct and recovers the classical Sperner theorem when G is complete. They also define G-CFF by adding the union-containment restriction on edges and give the trivial sandwich t(1,n) ≤ t(G) ≤ t(2,n) for graphs without isolates, with equality cases for stars on the lower side and completes on the upper side. The concrete advance is the mixed-radix Gray-code construction that brings the upper bound for paths and cycles down to 1.893 log₂ n + O(1), well below the general 5.512 log₂ n from Erdős-Frankl-Füredi. That construction is explicit and looks reproducible. The paper does a clean job unifying the two classical notions under one graph parameter and supplying workable families for several infinite graph classes. The softer spots are that t(G) remains only bounded in general, with no exact closed form except for the Sperner case, and the constructions are tailored rather than asymptotically optimal for arbitrary G. No circularity appears; the upper bounds rest on independent encodings. This is for people already working in extremal set theory who want a graph-theoretic handle on these parameters. It is not broad-impact work, but the exact result and the improved constructions are verifiable and worth checking in detail. I would send it to referees.

Referee Report

1 major / 3 minor

Summary. This paper introduces G-Sperner and G-CFF families as graph-theoretic generalizations of Sperner families and cover-free families. The central result is the proof that t_s(G) equals t(1, χ(G)) for any simple graph G. For the G-CFF parameter t(G), the authors establish the trivial bound t(1,n) ≤ t(G) ≤ t(2,n) for graphs without isolated vertices, demonstrate tightness for certain stars and complete graphs, and derive improved upper bounds for paths, cycles, wheels, and windmill graphs, including a mixed-radix Gray code construction giving t(P_n) and t(C_n) at most 1.893 log₂ n plus lower order terms.

Significance. The equality t_s(G) = t(1, χ(G)) offers a precise link between graph chromatic number and the minimal dimension for Sperner families, based on homomorphisms to incomparability graphs and Dilworth's theorem. This is a solid structural contribution. The explicit constructions for t(G) on specific graphs provide quantitative improvements over the Erdős-Frankl-Füredi bounds for 2-CFF and may find use in applications requiring structured set systems with controlled containments.

major comments (1)

The assertion that t(1, n) ≤ t(G) holds for any simple G with no isolated vertices requires a detailed proof or argument. While G-CFF implies G-Sperner, and thus t(G) ≥ t_s(G) = t(1, χ(G)), the stronger lower bound t(1, n) does not follow directly unless the family is necessarily an antichain. Since non-edges permit potential containments (subject to the union conditions on edges), an explicit demonstration that no such containments can occur or that the size is still bounded by the Sperner capacity is needed. This underpins the tightness for star graphs.

minor comments (3)

The sentence defining G-CFF could be split for clarity, and an example for a small graph (e.g., a path on 3 vertices) would help illustrate the union condition.
The mixed-radix Gray code construction should include a brief verification that the generated subsets satisfy the non-containment and union conditions for adjacent vertices in the path or cycle.
Ensure that Dilworth's theorem and any Gray code references are cited if used in the proofs.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and helpful comments. We address the single major comment below.

read point-by-point responses

Referee: The assertion that t(1, n) ≤ t(G) holds for any simple G with no isolated vertices requires a detailed proof or argument. While G-CFF implies G-Sperner, and thus t(G) ≥ t_s(G) = t(1, χ(G)), the stronger lower bound t(1, n) does not follow directly unless the family is necessarily an antichain. Since non-edges permit potential containments (subject to the union conditions on edges), an explicit demonstration that no such containments can occur or that the size is still bounded by the Sperner capacity is needed. This underpins the tightness for star graphs.

Authors: We agree that the claim requires an explicit argument rather than being entirely trivial, and we will add a detailed proof in the revised manuscript. The argument is as follows: suppose a G-CFF family admits a containment A ⊂ B. Because G has no isolated vertices, the vertex for B has a neighbor C. The G-CFF condition on the edge {B,C} requires that B ∪ C contains no other member of the family. Yet A ⊂ B ⊂ B ∪ C with A distinct from both B and C, a contradiction. Hence every G-CFF family on a graph without isolated vertices is necessarily an antichain, so t(G) ≥ t(1,n) by Sperner's theorem. This also justifies the matching lower bound used for the star graphs (where we separately exhibit constructions achieving the upper bound t(1,n)). We will insert this short proof immediately after the statement of the trivial bound. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses independent external theorems

full rationale

The paper's central claim t_s(G) = t(1, χ(G)) follows directly from viewing G-Sperner families as homomorphisms into the incomparability graph of the boolean lattice and applying Dilworth's theorem (χ equals max antichain size) together with Sperner's theorem; these are standard, externally verified poset results with no dependence on the paper's own constructions or fitted parameters. Upper and lower bounds for t(G) are supplied by explicit combinatorial encodings (mixed-radix Gray codes, colorings) that are built independently of the target quantity t(1, χ(G)). No self-definitional steps, fitted-input predictions, or load-bearing self-citations appear in the derivation chain. The trivial bound t(1,n) ≤ t(G) ≤ t(2,n) is stated as an immediate consequence of the definitions and holds by construction only in the trivial sense that does not affect the main equality.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Relies on Sperner's theorem for the base case and standard graph-coloring facts; no free parameters or invented entities are introduced.

axioms (1)

standard math Sperner's theorem: the largest antichain in the power set of a t-set has size binomial(t, floor(t/2))
Used to obtain t(1,n) ~ log2(n)

pith-pipeline@v0.9.0 · 5850 in / 1193 out tokens · 58169 ms · 2026-05-14T20:25:35.930574+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references · 1 canonical work pages

[1]

Linear time constructions of some-restriction problems

Nader H Bshouty. Linear time constructions of some-restriction problems. InInternational Conference on Algorithms and Complexity, pages 74–88. Springer, 2015

2015
[2]

An efficient algorithm for group testing with runlength constraints.Discrete Applied Mathematics, 360:181–187, 2025

Marco Dalai, Stefano Della Fiore, Adele A Rescigno, and Ugo Vaccaro. An efficient algorithm for group testing with runlength constraints.Discrete Applied Mathematics, 360:181–187, 2025

2025
[3]

A decomposition theorem for partially ordered sets.Classic papers in combinatorics, pages 139–144, 1987

Robert P Dilworth. A decomposition theorem for partially ordered sets.Classic papers in combinatorics, pages 139–144, 1987

1987
[4]

World Scientific, 2000

Dingzhu Du and Frank Hwang.Combinatorial group testing and its applications, volume 12. World Scientific, 2000

2000
[5]

Bounds on the length of disjunctive codes.Problemy Peredachi Informatsii, 18(3):7–13, 1982

Arkadii Georgievich D’yachkov and Vladimir Vasil’evich Rykov. Bounds on the length of disjunctive codes.Problemy Peredachi Informatsii, 18(3):7–13, 1982

1982
[6]

Families of finite sets in which no set is covered by the union of two others.Journal of Combinatorial Theory, Series A, 33(2):158–166, 1982

Paul Erd¨ os, Peter Frankl, and Zolt´ an F¨ uredi. Families of finite sets in which no set is covered by the union of two others.Journal of Combinatorial Theory, Series A, 33(2):158–166, 1982

1982
[7]

Erd¨ os, P

P. Erd¨ os, P. Frankl, and Z. F¨ uredi. Families of finite sets in which no set is covered by the union of r others.Israel Journal of Mathematics, 51(1-2):79–89, 1985

1985
[8]

On r-cover-free families.Journal of Combinatorial Theory, Series A, 73(1):172–173, 1996

Zolt´ an F¨ uredi. On r-cover-free families.Journal of Combinatorial Theory, Series A, 73(1):172–173, 1996

1996
[9]

Low-weight superimposed codes and their applications

Luisa Gargano, Adele A Rescigno, and Ugo Vaccaro. Low-weight superimposed codes and their applications. InInternational Workshop on Frontiers in Algorithmics, pages 197–211. Springer, 2018

2018
[10]

Oxford University Press, 2026

Pavol Hell and Jaroslav Neˇ setˇ ril.Graphs and Homomorphisms, volume 34 ofOxford Grad- uate Texts in Mathematics Series. Oxford University Press, 2026

2026
[11]

F. K. Hwang and Vera T. S´ os. Non-adaptive hypergeometric group testing.Studia Scien- tiarum Mathematicarum Hungarica, 22(1-4):257–263, 1987

1987
[12]

Structure-aware combinatorial group testing: a new method for pandemic screening

Tha´ ıs Bardini Idalino and Lucia Moura. Structure-aware combinatorial group testing: a new method for pandemic screening. InInternational Workshop on Combinatorial Algorithms, pages 143–156. Springer, 2022

2022
[13]

A survey of cover-free families: constructions, applications, and generalizations

Tha´ ıs Bardini Idalino and Lucia Moura. A survey of cover-free families: constructions, applications, and generalizations. InInternational Conference on New Advances in Designs, Codes and Cryptography, pages 195–239. Springer, 2022

2022
[14]

Cover-free families on hypergraphs and combina- torial group testing.To appear in Journal of Combinatorial Optimization, 2026

Tha´ ıs Bardini Idalino and Lucia Moura. Cover-free families on hypergraphs and combina- torial group testing.To appear in Journal of Combinatorial Optimization, 2026

2026
[15]

CRC Press, 2008

Wilfried Imrich, Sandi Klavzar, and Douglas F Rall.Topics in graph theory: Graphs and their Cartesian product. CRC Press, 2008. 34 PRANGYA PARIDA AND LUCIA MOURA

2008
[16]

W. H. Kautz and R. C. Singleton. Nonrandom binary superimposed codes.IEEE Transac- tions on Information Theory, 10(4):363–377, 1964

1964
[17]

Pearson Education India, 2011

Donald E Knuth.The art of computer programming, volume 4A: combinatorial algorithms, part 1. Pearson Education India, 2011

2011
[18]

Constructions of 2-cover-free families and related separating hash families.Journal of Combinatorial Designs, 14(6):423–440, 2006

PC Li, GHJ Van Rees, and R Wei. Constructions of 2-cover-free families and related separating hash families.Journal of Combinatorial Designs, 14(6):423–440, 2006

2006
[19]

Meagher and B

K. Meagher and B. Stevens. Covering arrays on graphs.Journal of Combinatorial Theory Series B, 2005

2005
[20]

Explicit nonadaptive combinatorial group testing schemes

Ely Porat and Amir Rothschild. Explicit nonadaptive combinatorial group testing schemes. IEEE Transactions on Information Theory, 57(12):7982–7989, 2011

2011
[21]

Bounds and algorithms for generalized superimposed codes.Information Processing Letters, 182:106365, 2023

Adele A Rescigno and Ugo Vaccaro. Bounds and algorithms for generalized superimposed codes.Information Processing Letters, 182:106365, 2023

2023
[22]

On the upper bound of the size of the r-cover-free families.Journal of Combinatorial Theory, Series A, 66(2):302–310, 1994

Mikl´ os Ruszink´ o. On the upper bound of the size of the r-cover-free families.Journal of Combinatorial Theory, Series A, 66(2):302–310, 1994

1994
[23]

J. Scholes. 18th imo 1976, problem 4, 1976. Available electronically athttps://prase.cz/ kalva/imo/isoln/isoln764.html

1976
[24]

J. Scholes. 40th putnam 1979 problem a1, 1979. Available electronically athttps://prase. cz/kalva/putnam/psoln/psol791.html

1979
[25]

N. J. A. Sloane. On-line encyclopedia of integer sequences. Available electronically at https://oeis.org/A000792
[26]

Ein satz ¨ uber untermengen einer endlichen menge.Mathematische Zeitschrift, 27(1):544–548, 1928

Emanuel Sperner. Ein satz ¨ uber untermengen einer endlichen menge.Mathematische Zeitschrift, 27(1):544–548, 1928

1928
[27]

Generalized cover-free families.Discrete Mathematics, 279(1-3):463–477, 2004

Douglas R Stinson and Ruizhong Wei. Generalized cover-free families.Discrete Mathematics, 279(1-3):463–477, 2004

2004
[28]

Some new bounds for cover-free families

Douglas R Stinson, Ruizhong Wei, and Lie Zhu. Some new bounds for cover-free families. J. Comb. Theory, Ser. A, 90(1):224–234, 2000

2000
[29]

R. Wei. On cover-free families.arXiv:2303.17524, 2006. AppendixA.Proof of Propositions 6.3 and 6.6 A.1.Proof of Proposition 6.3. Proof.From Construction 6.2, it is easy to see that the first codeword is always the zero tuple, and the last codeword is ann-tuple starting withm 1 −1, followed by all zeros (ifm 1 is even), since we append the reverse order of...

work page arXiv 2006