Date:

Mon, 09/01/201711:00-13:00

Location:

Rothberg B220 (CS bldg)

Speaker: Ilan Karpas, HU

Tilte: Families with forbidden intersection patterns

Abstract:

Let l, n be even natural numbers. A pattern p of length l is an element

p = (p1, . . . , pl) ∈ {−, +}^l. Given such a pattern and two sets A, B ⊂ [n], we say that the pair (A, B) forms pattern p if the following conditions are satisfied:

1. A \Delta B = {i_1, . . . , i_l}, where i_1 < i_2 < . . . < i_l,

2. For 1 ≤ j ≤ l, we have i_ j ∈ A \ B if p_ j = + and i_ j ∈ B \ A if p_ j = −.

We will say that a family F ⊂ 2^[n] avoids pattern p if there are no sets A, B ∈ F so that (A, B) forms pattern p. From now on, we assume that F is a family of (n/2)-subsets of [n] and that p has (l/2) −s and (l/2) +s.

How large can a family F ⊂ 2^[n] [n] be if it avoids pattern p? We say that there is a density theorem for p if every such family satisfies |F| = o(n \choose (n/2)). Otherwise, we say that there is no density theorem for p.

In this talk I will discuss a number of situations in which such density theorems exist. We show that if p is a pattern consisting of (l/2) +s followed by (l/2) −s (i.e. p = (+ + · · · + − − · · · −)), then for l = o(√n) there is a density theorem for p, while for l = Ω(√n) there is no density theorem for p. For patterns p of length l which alternate between + and − (i.e. p = (+ − + − . . . + −)), we show that there is a density theorem if l = o(√n) and that there is no density theorem if l = Ω(n). Lastly, we show that for a fixed pattern p of constant length, there is a density theorem for p, provided n is large enough.

The talk is based on a paper to be published in the European Journal of Combinatorics. Joint work with Eoin long.

Tilte: Families with forbidden intersection patterns

Abstract:

Let l, n be even natural numbers. A pattern p of length l is an element

p = (p1, . . . , pl) ∈ {−, +}^l. Given such a pattern and two sets A, B ⊂ [n], we say that the pair (A, B) forms pattern p if the following conditions are satisfied:

1. A \Delta B = {i_1, . . . , i_l}, where i_1 < i_2 < . . . < i_l,

2. For 1 ≤ j ≤ l, we have i_ j ∈ A \ B if p_ j = + and i_ j ∈ B \ A if p_ j = −.

We will say that a family F ⊂ 2^[n] avoids pattern p if there are no sets A, B ∈ F so that (A, B) forms pattern p. From now on, we assume that F is a family of (n/2)-subsets of [n] and that p has (l/2) −s and (l/2) +s.

How large can a family F ⊂ 2^[n] [n] be if it avoids pattern p? We say that there is a density theorem for p if every such family satisfies |F| = o(n \choose (n/2)). Otherwise, we say that there is no density theorem for p.

In this talk I will discuss a number of situations in which such density theorems exist. We show that if p is a pattern consisting of (l/2) +s followed by (l/2) −s (i.e. p = (+ + · · · + − − · · · −)), then for l = o(√n) there is a density theorem for p, while for l = Ω(√n) there is no density theorem for p. For patterns p of length l which alternate between + and − (i.e. p = (+ − + − . . . + −)), we show that there is a density theorem if l = o(√n) and that there is no density theorem if l = Ω(n). Lastly, we show that for a fixed pattern p of constant length, there is a density theorem for p, provided n is large enough.

The talk is based on a paper to be published in the European Journal of Combinatorics. Joint work with Eoin long.