Set families with a forbidden pattern
A balanced pattern of order 2d is an element P ∈ {+, −}2d , where both signs appear d times. Two sets A, B ⊂ [n] form a P-pattern, which we denote by pat(A, B) = P, if A△B = {j1, . . . , j2d} with 1 ≤ j1 < · · · < j2d ≤ n and {i ∈ [2d] : Pi = +} = {i ∈ [2d] : ji ∈ A \ B}. We say A ⊂ P...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2017
|
| _version_ | 1797101333131558912 |
|---|---|
| author | Karpas, I Long, E |
| author_facet | Karpas, I Long, E |
| author_sort | Karpas, I |
| collection | OXFORD |
| description | A balanced pattern of order 2d is an element P ∈ {+, −}2d , where both signs appear d times. Two sets A, B ⊂ [n] form a P-pattern, which we denote by pat(A, B) = P, if A△B = {j1, . . . , j2d} with 1 ≤ j1 < · · · < j2d ≤ n and {i ∈ [2d] : Pi = +} = {i ∈ [2d] : ji ∈ A \ B}. We say A ⊂ P [n] is P-free if pat(A, B) ̸= P for all A, B ∈ A. We consider the following extremal question: how large can a family A ⊂ P [n] be if A is P-free? We prove a number of results on the sizes of such families. In particular, we show that for some fixed c > 0, if P is a d-balanced pattern with d < c log log n then | A |= o(2 n ). We then give stronger bounds in the cases when (i) P consists of d+ signs, followed by d− signs and (ii) P consists of alternating signs. In both cases, if d = o( √ n)then | A |= o(2 n ). In the case of (i), this is tight. |
| first_indexed | 2024-03-07T05:50:22Z |
| format | Journal article |
| id | oxford-uuid:e8a916cc-b3cf-4e8c-88ef-7d4710a1f189 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:50:22Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:e8a916cc-b3cf-4e8c-88ef-7d4710a1f1892022-03-27T10:48:27ZSet families with a forbidden patternJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e8a916cc-b3cf-4e8c-88ef-7d4710a1f189Symplectic Elements at OxfordElsevier2017Karpas, ILong, EA balanced pattern of order 2d is an element P ∈ {+, −}2d , where both signs appear d times. Two sets A, B ⊂ [n] form a P-pattern, which we denote by pat(A, B) = P, if A△B = {j1, . . . , j2d} with 1 ≤ j1 < · · · < j2d ≤ n and {i ∈ [2d] : Pi = +} = {i ∈ [2d] : ji ∈ A \ B}. We say A ⊂ P [n] is P-free if pat(A, B) ̸= P for all A, B ∈ A. We consider the following extremal question: how large can a family A ⊂ P [n] be if A is P-free? We prove a number of results on the sizes of such families. In particular, we show that for some fixed c > 0, if P is a d-balanced pattern with d < c log log n then | A |= o(2 n ). We then give stronger bounds in the cases when (i) P consists of d+ signs, followed by d− signs and (ii) P consists of alternating signs. In both cases, if d = o( √ n)then | A |= o(2 n ). In the case of (i), this is tight. |
| spellingShingle | Karpas, I Long, E Set families with a forbidden pattern |
| title | Set families with a forbidden pattern |
| title_full | Set families with a forbidden pattern |
| title_fullStr | Set families with a forbidden pattern |
| title_full_unstemmed | Set families with a forbidden pattern |
| title_short | Set families with a forbidden pattern |
| title_sort | set families with a forbidden pattern |
| work_keys_str_mv | AT karpasi setfamilieswithaforbiddenpattern AT longe setfamilieswithaforbiddenpattern |