Source author record

Grzegorz Matecki

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

On the Duality of Semiantichains and Unichain Coverings

We study a min-max relation conjectured by Saks and West: For any two posets $P$ and $Q$ the size of a maximum semiantichain and the size of a minimum unichain covering in the product $P\times Q$ are equal. For positive we state conditions on $P$ and $Q$ that imply the min-max relation. Based on these conditions we identify some new families of posets where the conjecture holds and get easy proofs for several instances where the conjecture had been verified before. However, we also have examples showing that in general the min-max relation is false, i.e., we disprove the Saks-West conjecture.

preprint2012arXiv

Additive colorings of planar graphs

An \emph{additive coloring} of a graph $G$ is an assignment of positive integers $\{1,2,...,k\}$ to the vertices of $G$ such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number $k$ for which there exists an additive coloring of $G$ is denoted by $η(G)$ . We prove that $η(G)\leqslant 468$ for every planar graph $G$ . This improves a previous bound $η(G)\leqslant 5544$ due to Norin. The proof uses Combinatorial Nullstellensatz and coloring number of planar hypergrahs. We also demonstrate that $η(G)\leqslant 36$ for 3-colorable planar graphs, and $η(G)\leqslant 4$ for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each $r\geqslant 2$ there is an $r$ -chromatic graph $G_{r}$ with no additive coloring by elements of any Abelian group of order $r$ .

preprint2011arXiv

On-line Chain Partitions of Up-growing Semi-orders

On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents a partially ordered set, point by point. Algorithm assigns incoming points (immediately and irrevocably) to the chains which constitute a chain partition of the order. The value of the game for orders of width $w$ is a minimum number $\fVal(w)$ such that Algorithm has a strategy using at most $\fVal(w)$ chains on orders of width at most $w$ . We analyze the chain partition game for up-growing semi-orders. Surprisingly, the golden ratio comes into play and the value of the game is $\lfloor\frac{1+\sqrt{5}}{2}\; w \rfloor$ .

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.