On extremal problems concerning the traces of sets

S. Piga, B. Schülke

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given two non-negative integers n and s, define m(n, s) to be the maximal number m such that every hypergraph ℋ on n vertices and with at most m edges has a vertex x such that |ℋx|≥|E(ℋ)|−s, where ℋx={H∖{x}:H∈E(ℋx)}. The problem of determining the limit m(s)=limn→∞m(n,s)/n was posed by Füredi and Pach and by Frankl and Tokushige. While the first results were only for specific small values of s, Frankl determined m(2d−1−1) for all d∈ℕ. Here we prove that m(2d−1−c)=(2d−c)/d for every c,d∈ℕ with d≥4c and give an example showing that this equality does not hold anymore for d=c.

The other line of research on this problem is to determine m(s) for small values of s. In this line, our second result determines m(2d−1−c) for c∈{3,4}. This solves more instances of the problem for small s and in particular solves a conjecture by Frankl and Watanabe.
Original languageEnglish
Title of host publicationExtended Abstracts EuroComb 2021
Subtitle of host publicationEuropean Conference on Combinatorics, Graph Theory and Applications
EditorsJaroslav Nešetřil, Guillem Perarnau, Juanjo Rué, Oriol Serra
Number of pages6
ISBN (Electronic)9783030838232
ISBN (Print)9783030838225
Publication statusPublished - 24 Aug 2021

Publication series

NameTrends in Mathematics
ISSN (Print)2297-0215
ISSN (Electronic)2297-024X
NameResearch Perspectives CRM Barcelona
ISSN (Print)2509-7407
ISSN (Electronic)2509-7415


  • Extremal set theory
  • Traces of sets
  • Abstract simplicial complexes


Dive into the research topics of 'On extremal problems concerning the traces of sets'. Together they form a unique fingerprint.

Cite this