J. Grytczuk

activity

20112026

most citedA new approach to nonrepetitive sequences

42 citations · 109 across the 37 of their papers we have counts for

collaborators

Showing math.COShow all

47 papers · 1 filter

math.CO2026

A rainbow partition theorem for trees and connected maximin share allocations of chores

Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek +3

Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to $n$ …

math.CO2026

Packing arithmetic progressions

Noga Alon, Michał Dębski, Jarosław Grytczuk +1

Let $F = {A_{1}, A_{2}, \dots, A_{k}}$ be a collection of finite arithmetic progressions, where each $A_{d}$ is an initial segment of the set $D_{d} = {d, 2 d, 3 d, \dots}$ of consecutiv…

math.CO2026

Homogeneous substructures in random ordered uniform matchings

Andrzej Dudek, Jarosław Grytczuk, Jakub Przybyło +1

An ordered $r$ -uniform matching of size $n$ is a collection of $n$ pairwise disjoint $r$ -subsets of a linearly ordered set of $r n$ vertices. For $n = 2$ , such a matching is called an…

math.CO2025

Neighborly boxes and strings with jokers; constructions and asymptotics

Jarosław Grytczuk, Andrzej P. Kisielewicz, Krzysztof Przesławski

We study families of axis-aligned boxes in a $d$ -dimensional Euclidean space $R^{d}$ whose placement is restricted by bounds on the dimension of their pairwise intersections…

math.CO2025

Homogeneous substructures in random ordered hyper-matchings

Andrzej Dudek, Jarosław Grytczuk, Jakub Przybyło +1

An ordered $r$ -uniform matching of size $n$ is a collection of $n$ pairwise disjoint $r$ -subsets of a linearly ordered set of $r n$ vertices. For $n = 2$ , such a matching is called an…

math.CO2024

Words Avoiding Tangrams

Michał Dębski, Jarosław Grytczuk, Bartłomiej Pawlik +2

A \emph{tangram} is a word in which every letter occurs an even number of times. Such word can be cut into parts that can be arranged into two identical words. The minimum number o…

math.CO2024

Neighborly boxes and bipartite coverings; constructions and conjectures

Jarosław Grytczuk, Andrzej P. Kisielewicz, Krzysztof Przesławski

Two axis-aligned boxes in $R^{d}$ are \emph{ $k$ -neighborly} if their intersection has dimension at least $d - k$ and at most $d - 1$ . The maximum number of pairwise $k$ -neighbor…

math.CO2024

Largest bipartite sub-matchings of a random ordered matching or a problem with socks

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

Let $M$ be an ordered matching of size $n$ , that is, a partition of the set $[2 n]$ into 2-element subsets. The sock number of $M$ is the maximum size of a sub-matching of $M$ in wh…

math.CO2023

Twins in ordered hyper-matchings

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

An ordered $r$ -matching of size $n$ is an $r$ -uniform hypergraph on a linearly ordered set of vertices, consisting of $n$ pairwise disjoint edges. Two ordered $r$ -matchings are iso…

math.CO2023

Variations on shuffle squares

Jarosław Grytczuk, Bartłomiej Pawlik, Mariusz Pleszczyński

We study decompositions of words into subwords that are in some sense similar, which means that one subword may be obtained from the other by a relatively simple transformation. Ou…

math.CO2023

Cooperative coloring of matroids

Tomasz Bartnicki, Sebastian Czerwiński, Jarosław Grytczuk +1

Let $M_{1}, M_{2}, \dots, M_{k}$ be a collection of matroids on the same ground set $E$ . A coloring $c : E \to {1, 2, \dots, k}$ is called \emph{cooperative} if for every color $j$ ,…

math.CO2023

Strong arboricity of graphs

Tomasz Bartnicki, Sebastian Czerwiński, Jarosław Grytczuk +1

An edge coloring of a graph $G$ is \emph{woody} if no cycle is monochromatic. The \emph{arboricity} of a graph $G$ , denoted by $\arb (G)$, is the least number of colors needed for…

math.CO2023

Strongly proper connected coloring of graphs

Michał Dębski, Jarosław Grytczuk, Paweł Naroski +1

We study a new variant of \emph{connected coloring} of graphs based on the concept of \emph{strong} edge coloring (every color class forms an \emph{induced} matching). In particula…

math.CO2023★ 2 cited

Erdős-Szekeres type Theorems for ordered uniform matchings

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

For $r, n \geq 2$ , an ordered $r$ -uniform matching of size $n$ is an $r$ -uniform hypergraph on a linearly ordered vertex set $V$ , with $∣ V ∣ = r n$ , consisting of $n$ pairwise disjoint edg…

math.CO2022★ 1 cited

New bounds on the maximum number of neighborly boxes in R^d

Noga Alon, Jarosław Grytczuk, Andrzej P. Kisielewicz +1

A family of axis-aligned boxes in $\er^d$ is \emph{ $k$ -neighborly} if the intersection of every two of them has dimension at least $d - k$ and at most $d - 1$ . Let $n (k, d)$ denote the…

math.CO2022★ 1 cited

Ordered unavoidable sub-structures in matchings and random matchings

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

An ordered matching of size $n$ is a graph on a linearly ordered vertex set $V$ , $∣ V ∣ = 2 n$ , consisting of $n$ pairwise disjoint edges. There are three different ordered matchings of…

math.CO2022

Extensions and reductions of square-free words

Michał Dębski, Jarosław Grytczuk, Bartłomiej Pawlik

A word is square-free if it does not contain a nonempty word of the form $X X$ as a factor. A famous 1906 result of Thue asserts that there exist arbitrarily long square-free words…

math.CO2022

Mrs. Correct and Majority Colorings

Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk +3

A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techn…

math.CO2021

Long twins in random words

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

Twins in a finite word are formed by a pair of identical subwords placed at disjoint sets of positions. We investigate the maximum length of twins in a random word over a $k$ -lette…

math.CO2021

Multiple twins in permutations

Andrzej Dudek, Jaroslaw Grytczuk, Andrzej Rucinski

By an $r$ -tuplet in a permutation we mean a family of $r$ pairwise disjoint subsequences with the same relative order. The length of an $r$ -tuplet is defined as the length of any s…

math.CO2021

Tight multiple twins in permutations

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

Two permutations are similar if they have the same length and the same relative order. A collection of $r \geq 2$ disjoint, similar subsequences of a permutation $π$ form $r$ -twins in…

math.CO2021

Square-free extensions of words

Jarosław Grytczuk, Hubert Kordulewski, Bartłomiej Pawlik

A word is square-free if it does not contain nonempty factors of the form $X X$ . In 1906 Thue proved that there exist arbitrarily long square-free words over a $3$ -letter alphabet.…

math.CO2020

On weak twins and up-and-down sub-permutations

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

Two permutations $(x_{1}, \dots, x_{w})$ and $(y_{1}, \dots, y_{w})$ are weakly similar if $x_{i} < x_{i + 1}$ if and only if $y_{i} < y_{i + 1}$ for all $1 ⩽ i ⩽ w$ . Let $π$ be a permutati…

math.CO2020★ 5 cited

Graph Polynomials and Group Coloring of Graphs

Bartłomiej Bosek, Jarosław Grytczuk, Grzegorz Gutowski +2

Let $Γ$ be an Abelian group and let $G$ be a simple graph. We say that $G$ is $Γ$ -colorable if for some fixed orientation of $G$ and every edge labeling $ℓ : E (G) \to Γ$ , t…