Source author record

Andrzej Kisielewicz

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

ResearcherUnclaimed source record

math.CO Formal Languages and Automata Theory Data Structures and Algorithms Discrete Mathematics math.GR

Catalog footprint

Research overview

9works

5topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Distinguishing actions of symmetric groups and related graphs

The distinguishing number $D(G,X)$ of an action of a group $G$ on a set $X$ is the least size of a partition of $X$ such that no element of $G$ acting nontrivially on $X$ preserves this partition. In this paper we describe the distinguishing numbers for all actions of the symmetric group $S_n$ , for any $n\geq 3$ . This allows us to describe the distinguishing numbers for all graphs whose automorphism group is isomorphic with a symmetric group. Our description solves a few open problems posed by various authors in earlier papers on this topic.

preprint2020arXiv

Distinguishing simple groups

The distinguishing number $D(Γ)$ of a graph $Γ$ is the least size of a partition of the vertices of $Γ$ such that no non-trivial automorphism of $Γ$ preserves this partition. We show that if the automorphism group of a graph $Γ$ is simple, than $D(Γ)=2$ . This is obtained by establishing the distinguishing number for all possible actions of simple groups.

preprint2016arXiv

Experiments with Synchronizing Automata

We have improved an algorithm generating synchronizing automata with a large length of the shortest reset words. This has been done by refining some known results concerning bounds on the reset length. Our improvements make possible to consider a number of conjectures and open questions concerning synchronizing automata, checking them for automata with a small number of states and discussing the results. In particular, we have verified the Černý conjecture for all binary automata with at most 12 states, and all ternary automata with at most 8 states.

preprint2016arXiv

Synchronizing Automata with Extremal Properties

We present a few classes of synchronizing automata exhibiting certain extremal properties with regard to synchronization. The first is a series of automata with subsets whose shortest extending words are of length $\varTheta(n^2)$ , where $n$ is the number of states of the automaton. This disproves a conjecture that every subset in a strongly connected synchronizing automaton is $cn$ -extendable, for some constant $c$ , and in particular, shows that the cubic upper bound on the length of the shortest reset words cannot be improved generally by means of the extension method. A detailed analysis shows that the automata in the series have subsets that require words as long as $n^2/4+O(n)$ in order to be extended by at least one element. We also discuss possible relaxations of the conjecture, and propose the image-extension conjecture, which would lead to a quadratic upper bound on the length of the shortest reset words. In this regard we present another class of automata, which turn out to be counterexamples to a key claim in a recent attempt to improve the Pin-Frankl bound for reset words. Finally, we present two new series of slowly irreducibly synchronizing automata over a ternary alphabet, whose lengths of the shortest reset words are $n^2-3n+3$ and $n^2-3n+2$ , respectively. These are the first examples of such series of automata for alphabets of size larger than two.

preprint2014arXiv

A Fast Algorithm Finding the Shortest Reset Words

In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is exponential. Yet, it is faster than the algorithms used so far and it works well in practice. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare resulted subsets. We give both theoretical and practical arguments showing that the branching factor is reduced efficiently. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with $n$ states and 2 input letters. We follow Skvorsov and Tipikin, who have performed such a study using a SAT solver and considering automata up to $n=100$ states. With our algorithm we are able to consider much larger sample of automata with up to $n=300$ states. In particular, we obtain a new more precise estimation of the expected length of the shortest reset word $\approx 2.5\sqrt{n-5}$ .

preprint2013arXiv

Symmetry groups of Boolean Functions

We prove that every abelian permutation group, but known exceptions, is the symmetry group of a boolean function. This solves the problem posed in the book by Clote and Kranakis. In fact, our result is proved for a larger class of groups, namely, for all groups contained in direct sums of regular groups.

preprint2012arXiv

All totally symmetric colored graphs

In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, where we have shown, in particular, that there are no such graphs with more than 5 colors. Using some recent results, with a help of computer, we settle all the cases that was left open in the previous paper.

preprint2012arXiv

Rainbow Induced Subgraphs in Replication Graphs

A graph $G$ is called a replication graph of a graph $H$ if $G$ is obtained from $H$ by replacing vertices of $H$ by arbitrary cliques of vertices and then replacing each edge in $H$ by all the edges between corresponding cligues. For a given graph $H$ the $ρ_R(H)$ is the minimal number of vertices of a replication graph $G$ of $H$ such that every proper vertex coloring of $G$ contains a rainbow induced subgraph isomorphic to $H$ having exactly one vertex in each replication clique of $G$ . We prove some bounds for $ρ_R$ for some classes of graphs and compute some exact values. Also some experimental results obtained by a computer search are presented and conjectures based on them are formulated.

preprint2011arXiv

Rainbow induced subgraphs in proper vertex colorings

For a given graph $H$ we define $ρ(H)$ to be the minimum order of a graph $G$ such that every proper vertex coloring of $G$ contains a rainbow induced subgraph isomorphic to $H$ . We give upper and lower bounds for $ρ(H)$ , compute the exact value for some classes of graphs, and consider an interesting combinatorial problem connected with computation of $ρ(H)$ for paths. This research is motivated by some ideas in on-line graph coloring algorithms.

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.