Source author record

Tamás Mészáros

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.AC

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Complete minors in digraphs with given dichromatic number

The dichromatic number $\vecχ(D)$ of a digraph $D$ is the smallest $k$ for which it admits a $k$ -coloring where every color class induces an acyclic subgraph. Inspired by Hadwiger's conjecture for undirected graphs, several groups of authors have recently studied the containment of directed graph minors in digraphs with given dichromatic number. In this short note we improve several of the existing bounds and prove almost linear bounds by reducing the problem to a recent result of Postle on Hadwiger's conjecture.

preprint2021arXiv

Subspace coverings with multiplicities

We study the problem of determining the minimum number $f(n,k,d)$ of affine subspaces of codimension $d$ that are required to cover all points of $\mathbb{F}_2^n\setminus \{\vec{0}\}$ at least $k$ times while covering the origin at most $k-1$ times. The case $k=1$ is a classic result of Jamison, which was independently obtained by Brouwer and Schrijver for $d = 1$ . The value of $f(n,1,1)$ also follows from a well-known theorem of Alon and Füredi about coverings of finite grids in affine spaces over arbitrary fields. Here we determine the value of this function exactly in various ranges of the parameters. In particular, we prove that for $k \ge 2^{n-d-1}$ we have $f(n,k,d)=2^d k - \left \lfloor \frac{k}{2^{n-d}} \right \rfloor$ , while for $n > 2^{2^d k-k-d+1}$ we have $f(n,k,d)= n + 2^dk-d-2$ , and also study the transition between these two ranges. While previous work in this direction has primarily employed the polynomial method, we prove our results through more direct combinatorial and probabilistic arguments, and also exploit a connection to coding theory.

preprint2021arXiv

Zero sum cycles in complete digraphs

Given a non-trivial finite Abelian group $(A,+)$ , let $n(A) \ge 2$ be the smallest integer such that for every labelling of the arcs of the bidirected complete graph of order $n(A)$ with elements from $A$ there exists a directed cycle for which the sum of the arc-labels is zero. The problem of determining $n(\mathbb{Z}_q)$ for integers $q \ge 2$ was recently considered by Alon and Krivelevich, who proved that $n(\mathbb{Z}_q)=O(q \log q)$ . Here we improve their bound and show that $n(\mathbb{Z}_q)$ grows linearly. More generally we prove that for every finite Abelian group $A$ we have $n(A) \le 8|A|$ , while if $|A|$ is prime then $n(A) \le \frac{3}{2}|A|$ . As a corollary we also obtain that every $K_{16q}$ -minor contains a cycle of length divisible by $q$ for every integer $q \ge 2$ , which improves a result by Alon and Krivelevich.

preprint2019arXiv

Boolean Dimension, Components and Blocks

We investigate the behavior of Boolean dimension with respect to components and blocks. To put our results in context, we note that for Dushnik-Miller dimension, we have that if $\dim(C)\le d$ for every component $C$ of a poset $P$ , then $\dim(P)\le \max\{2,d\}$ ; also if $\dim(B)\le d$ for every block $B$ of a poset $P$ , then $\dim(P)\le d+2$ . By way of constrast, local dimension is well behaved with respect to components, but not for blocks: if $\text{ldim}(C)\le d$ for every component $C$ of a poset $P$ , then $\text{ldim}(P)\le d+2$ ; however, for every $d\ge 4$ , there exists a poset $P$ with $\text{ldim}(P)=d$ and $\dim(B)\le 3$ for every block $B$ of $P$ . In this paper we show that Boolean dimension behaves like Dushnik-Miller dimension with respect to both components and blocks: if $\text{bdim}(C)\le d$ for every component $C$ of $P$ , then $\text{bdim}(P)\le 2+d+4\cdot2^d$ ; also if $\text{bdim}(B)\le d$ for every block of $P$ , then $\text{bdim}(P)\le 19+d+18\cdot 2^d$ .

preprint2014arXiv

Shattering-extremal set systems of VC dimension at most 2

We say that a set system $\mathcal{F}\subseteq 2^{[n]}$ shatters a given set $S\subseteq [n]$ if $2^S=\{F \cap S : F \in \mathcal{F}\}$ . The Sauer inequality states that in general, a set system $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly $|\mathcal{F}|$ sets. In this paper we characterize shattering-extremal set systems of Vapnik-Chervonenkis dimension $2$ in terms of their inclusion graphs, and as a corollary we answer an open question from \cite{VC1} about leaving out elements from shattering-extremal set systems in the case of families of Vapnik-Chervonenkis dimension $2$ .

preprint2012arXiv

Shattering-extremal set systems of small VC-dimension

We say that a set system $\mathcal{F}\subseteq 2^{[n]}$ shatters a given set $S\subseteq [n]$ if $2^S={F \cap S : F \in \mathcal{F}}$ . The Sauer inequality states that in general, a set system $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly $|\mathcal{F}|$ sets. We characterize shattering extremal set systems of Vapnik-Chervonenkis dimension 1 in terms of their inclusion graphs. Also from the perspective of extremality, we relate set systems of bounded Vapnik-Chervonenkis dimension to their projections.

preprint2011arXiv

Some extensions of Alon's Nullstellensatz

Alon's combinatorial Nullstellensatz, and in particular the resulting nonvanishing criterion is one of the most powerful algebraic tools in combinatorics, with many important applications. In this paper we extend the nonvanishing theorem in two directions. We prove a version allowing multiple points. Also, we establish a variant which is valid over arbitrary commutative rings, not merely over subrings of fields. As an application, we prove extensions of the theorem of Alon and Füredi on hyperplane coverings of discrete cubes.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Tamás Mészáros

Research overview

Is this your work?

7 publications

Complete minors in digraphs with given dichromatic number

Subspace coverings with multiplicities

Zero sum cycles in complete digraphs

Boolean Dimension, Components and Blocks

Shattering-extremal set systems of VC dimension at most 2

Shattering-extremal set systems of small VC-dimension

Some extensions of Alon's Nullstellensatz

See the researcher in context

Building this map preview