Abstract : 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.
https://hal.inria.fr/hal-01184450 Contributor : Coordination Episciences IamConnect in order to contact the contributor Submitted on : Friday, August 14, 2015 - 2:59:33 PM Last modification on : Monday, December 28, 2020 - 10:22:04 AM Long-term archiving on: : Sunday, November 15, 2015 - 11:14:26 AM
Gyula O.H. Katona, Krisztián Tichler. An extremal problem on trees and database theory. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.293-298, ⟨10.46298/dmtcs.3461⟩. ⟨hal-01184450⟩