T. Mészáros

collaborators

4 papers

math.CO2017

Two results about the hypercube

Jozsef Balogh, Tamas Meszaros, Adam Zsolt Wagner

First we consider families in the hypercube $Q_{n}$ with bounded VC dimension. Frankl raised the problem of estimating the number $m (n, k)$ of maximal families of VC dimension $k$ . Al…

math.CO2017

Shattering-extremal set systems from Sperner families

Christopher Kusch, Tamás Mészáros

We say that a set system $F \subseteq 2^{[n]}$ shatters a given set $S \subseteq [n]$ if $2^{S} = {F \cap S : F \in F}$ . The Sauer-Shelah lemma states that in gener…

math.CO2017

A Semi-Random Construction of Small Covering Arrays

Shagnik Das, Tamás Mészáros

Given a set $S$ of $v \geq 2$ symbols, and integers $k \geq t \geq 2$ and $N \geq 1$ , an $N \times k$ array $A \in S^{N \times k}$ is an $(N; t, k, v)$ -covering array if all sequences…

math.CO2012

Shattering-extremal set systems of small VC-dimension

Tamás Mészáros, Lajos Rónyai

We say that a set system $F \subseteq 2^{[n]}$ shatters a given set $S \subseteq [n]$ if $2^{S} = F \cap S : F \in F$ . The Sauer inequality states that in general,…