Source author record

Grzegorz Matecki

Grzegorz Matecki appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

What is connected

3works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

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