Source author record

Uwe Leck

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Minimizing the regularity of maximal regular antichains of 2- and 3-sets

Let $n\geqslant 3$ be a natural number. We study the problem to find the smallest $r$ such that there is a family $\mathcal{A}$ of 2-subsets and 3-subsets of $[n]=\{1,2,...,n\}$ with the following properties: (1) $\mathcal{A}$ is an antichain, i.e. no member of $\mathcal A$ is a subset of any other member of $\mathcal A$ , (2) $\mathcal A$ is maximal, i.e. for every $X\in 2^{[n]}\setminus\mathcal A$ there is an $A\in\mathcal A$ with $X\subseteq A$ or $A\subseteq X$ , and (3) $\mathcal A$ is $r$ -regular, i.e. every point $x\in[n]$ is contained in exactly $r$ members of $\mathcal A$ . We prove lower bounds on $r$ , and we describe constructions for regular maximal antichains with small regularity.

preprint2013arXiv

Maximal antichains of minimum size

Let $n\geqslant 4$ be a natural number, and let $K$ be a set $K\subseteq [n]:={1,2,...,n}$ . We study the problem to find the smallest possible size of a maximal family $\mathcal{A}$ of subsets of $[n]$ such that $\mathcal{A}$ contains only sets whose size is in $K$ , and $A\not\subseteq B$ for all ${A,B}\subseteq\mathcal{A}$ , i.e. $\mathcal{A}$ is an antichain. We present a general construction of such antichains for sets $K$ containing 2, but not 1. If $3\in K$ our construction asymptotically yields the smallest possible size of such a family, up to an $o(n^2)$ error. We conjecture our construction to be asymptotically optimal also for $3\not\in K$ , and we prove a weaker bound for the case $K={2,4}$ . Our asymptotic results are straightforward applications of the graph removal lemma to an equivalent reformulation of the problem in extremal graph theory which is interesting in its own right.

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.