On extremal problems concerning the traces of sets

Abstract: Given two non-negative integers

n

and

s

, define

m (n, s)

to be the maximal number such that in every hypergraph

m a t h c a l H

on

n

vertices and with at most

m (n, s)

edges there is a vertex

x

such that

| m a t h c a l H_{x} | g e q | E (m a t h c a l H) | - s

, where

m a t h c a l H_{x} = H s e t m i n u s x : H i n E (m a t h c a l H)

. This problem has been posed by F"uredi and Pach and by Frankl and Tokushige. While the first results were only for specific small values of

s

, Frankl determined

m (n, 2^{d - 1} - 1)

for all

d i n m a t h b b N

with

d m i d n

. Subsequently, the goal became to determine

m (n, 2^{d - 1} - c)

for larger

c

. Frankl and Watanabe determined

m (n, 2^{d - 1} - c)

for

c i n 0, 2

. Other general results were not known so far. Our main result sheds light on what happens further away from powers of two: We prove that

m (n, 2^{d - 1} - c) = f r a c n d (2^{d} - c)

for

d g e q 4 c

and

d m i d n

and give an example showing that this equality does not hold for

c = d

. The other line of research on this problem is to determine

m (n, s)

for small values of

s

. In this line, our second result determines

m (n, 2^{d - 1} - c)

for

c i n 3, 4

. This solves more instances of the problem for small

s

and in particular solves a conjecture by Frankl and Watanabe.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On extremal problems concerning the traces of sets