Gyula O.H. Katona ; Krisztián Tichler
-
An extremal problem on trees and database theory
dmtcs:3461 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3461
An extremal problem on trees and database theory
Authors: Gyula O.H. Katona 1; Krisztián Tichler 2
NULL##NULL
Gyula O.H. Katona;Krisztián Tichler
1 Alfréd Rényi Institute of Mathematics
2 Technical University of Berlin / Technische Universität Berlin
We consider an extremal problem on labelled directed trees and applications to database theory. Among others, we will show explicit keysystems on an underlying set of size $n$, that cannot be represented by a database of less than $2^{n(1-c\cdot \log \log n / \log n)}$ rows.