Kusch, Christopher and Mészáros, Tamás (2020) Shattering-extremal set systems from Sperner families. DISCRETE APPLIED MATHEMATICS, 276. pp. 92-101. ISSN 0166-218X
|
Text
1710.03165.pdf Download (202kB) | Preview |
Abstract
We say that a set system F subset of 2([n]) shatters a given set S subset of [n] if 2(S) = {F boolean AND S: F is an element of F}. The Sauer-Shelah lemma states that in general, a set system F shatters at least vertical bar F vertical bar sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly vertical bar F vertical bar sets. Here we discuss an approach to study these systems using Sperner families and prove some preliminary results based on an earlier algebraic approach. (C) 2019 Elsevier B.V. All rights reserved.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Sperner families; Shattering; Gröbner bases; Sauer-Shelah lemma; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 07 Feb 2023 14:57 |
| Last Modified: | 07 Feb 2023 14:57 |
| URI: | http://real.mtak.hu/id/eprint/158338 |
Actions (login required)
 |
Edit Item |
