Source author record

Petr Gregor

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

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Star transposition Gray codes for multiset permutations

Given integers $k\geq 2$ and $a_1,\ldots,a_k\geq 1$ , let $\boldsymbol{a}:=(a_1,\ldots,a_k)$ and $n:=a_1+\cdots+a_k$ . An $\boldsymbol{a}$ -multiset permutation is a string of length $n$ that contains exactly $a_i$ symbols $i$ for each $i=1,\ldots,k$ . In this work we consider the problem of exhaustively generating all $\boldsymbol{a}$ -multiset permutations by star transpositions, i.e., in each step, the first entry of the string is transposed with any other entry distinct from the first one. This is a far-ranging generalization of several known results. For example, it is known that permutations ( $a_1=\cdots=a_k=1$ ) can be generated by star transpositions, while combinations ( $k=2$ ) can be generated by these operations if and only if they are balanced ( $a_1=a_2$ ), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter $Δ(\boldsymbol{a}):=n-2\max\{a_1,\ldots,a_k\}$ that allows us to distinguish three different regimes for this problem. We show that if $Δ(\boldsymbol{a})<0$ , then a star transposition Gray code for $\boldsymbol{a}$ -multiset permutations does not exist. We also construct such Gray codes for the case $Δ(\boldsymbol{a})>0$ , assuming that they exist for the case $Δ(\boldsymbol{a})=0$ . For the case $Δ(\boldsymbol{a})=0$ we present some partial positive results. Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams. In particular, we prove that the middle levels graph is Hamilton-laceable.

preprint2021arXiv

Gray codes and symmetric chains

We consider the problem of constructing a cyclic listing of all bitstrings of length $2n+1$ with Hamming weights in the interval $[n+1-\ell,n+\ell]$ , where $1\leq \ell\leq n+1$ , by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (the case $\ell=1$ ). We provide a solution for the case $\ell=2$ , and we solve a relaxed version of the problem for general values of $\ell$ , by constructing cycle factors for those instances. The proof of the first result uses the lexical matchings introduced by Kierstead and Trotter, which we generalize to arbitrary consecutive levels of the hypercube. The proof of the second result uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets. We also present several new constructions of such decompositions based on lexical matchings. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the $n$ -dimensional hypercube for any $n\geq 12$ .

preprint2016arXiv

Modelling simultaneous broadcasting by level-disjoint partitions

Simultaneous broadcasting of multiple messages from the same source vertex in synchronous networks is considered under restrictions that each vertex receives at most one message in a unit time step, every received message can be sent out only in the next time step, no message is sent to already informed vertex. The number of outgoing messages in unrestricted, messages have unit length, and we assume full-duplex mode. In [9] we developed a concept of level-disjoint partitions to study simultaneous broadcasting under this model. In this work we consider the optimal number of level-disjoint partitions. We also provide a necessary condition in terms of eccentricity and girth on existence of $k$ $v$ -rooted level-disjoint partitions of optimal height. In particular, we provide a structural characterization of graphs admitting two level-disjoint partitions with the same root.

preprint2016arXiv

On incidence coloring conjecture in Cartesian products of graphs

An incidence in a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$ . Two incidences $(v,e)$ and $(u,f)$ are adjacent if at least one of the following holds: $(a)$ $v = u$ , $(b)$ $e = f$ , or $(c)$ $vu \in \{e,f\}$ . An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most $Δ(G) + 2$ colors are needed for an incidence coloring of any graph $G$ . The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph $G$ for which $G$ admits an incidence coloring with at most $Δ(G) + 2$ colors.

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.