T. Mészáros

activity

20122019

collaborators

Showing 2017 · math.COShow all

5 papers · 2 filters

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

Boolean dimension and tree-width

Stefan Felsner, Tamás Mészáros, Piotr Micek

The dimension is a key measure of complexity of partially ordered sets. Small dimension allows succinct encoding. Indeed if $P$ has dimension $d$ , then to know whether $x \leq y$ i…

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.CO2017

Separating Tree-chromatic number from Path-chromatic Number

Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros +4

We apply Ramsey theoretic tools to show that there is a family of graphs which have tree-chromatic number at most~ $2$ while the path-chromatic number is unbounded. This resolves a…