Bounds on the cover time of parallel rotor walks

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the initialization of the walks. We show that for any graph with m edges and diameter D, this cover time is at most $\mathrm{\Theta }(mD/\log k)$ and at least $\mathrm{\Theta }(mD/k)$, which corresponds to a speedup of between $\mathrm{\Theta }(\log k)$ and $\mathrm{\Theta }(k)$ with respect to the cover time of a single walk.     

Invariant and dual subtraction games resolving the Duchêne–Rigo conjecture

We prove a recent conjecture of Duchêne and Rigo, stating that every complementary pair of homogeneous Beatty sequences represents the solution to an invariant impartial game. Here invariance means that each available move in a game can be played anywhere inside the game board. In fact, we establish such a result for a wider class of pairs of complementary sequences, and in the process generalize the notion of a subtraction game. Given a pair of complementary sequences $\left(a_n\right)$ and $\left(b_n\right)$ of positive integers, we define a game $G$ by setting $\left\{\{a_n,b_n\}\right\}$ as invariant moves. We then introduce the invariant game $G^{?}$, whose moves are all non-zero $P$-positions of $G$. Provided the set of non-zero $P$-positions of $G^{?}$ equals $\left\{\{a_n,b_n\}\right\}$, this is the desired invariant game. We give sufficient conditions on the initial pair of sequences for this ‘duality’ to hold.     

On average and highest number of flips in pancake sorting

We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from the top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We are interested in the largest value of the number of flips needed to sort a stack of $n$ pancakes, both in the unburnt version ($f\left(n\right)$) and in the burnt version ($g\left(n\right)$).We present exact values of $f\left(n\right)$ up to $n=19$ and of $g\left(n\right)$ up to $n=17$ and disprove a conjecture of Cohen and Blum by showing that the burnt stack $?I_{15}$ is not the hardest to sort for $n=15$.We also show that sorting a random stack of $n$ unburnt pancakes can be done with at most $17n/12+O\left(1\right)$ flips on average. The average number of flips of the optimal algorithm for sorting stacks of $n$ burnt pancakes is shown to be between $n+\Omega (n/logn)$ and $7n/4+O\left(1\right)$ and we conjecture that it is $n+\Theta (n/logn)$.Finally we show that sorting the stack $?I_n$ needs at least $?(3n+3)/2?$ flips, which slightly increases the lower bound on $g\left(n\right)$. This bound together with the upper bound for sorting $?I_n$ found by Heydari and Sudborough in 1997 [10] gives the exact number of flips to sort it for $n\equiv 3(mod4)$ and $n\ge 15$.     

State complexity of power

The number of states in a deterministic finite automaton (DFA) recognizing the language $L^k$, where $L$ is regular language recognized by an $n$-state DFA, and $k?2$ is a constant, is shown to be at most $n{2}^{(k?1)n}$ and at least $(n?k)2^{(k?1)(n?k)}$ in the worst case, for every $n>k$ and for every alphabet of at least six letters. Thus, the state complexity of $L^k$ is $\Theta \left(n{2}^{(k?1)n}\right)$. In the case $k=3$ the corresponding state complexity function for $L^3$ is determined as $\frac{6n?3}{8}{4}^n?(n?1)2^n?n$ with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of $L^k$ is demonstrated to be $nk$. This bound is shown to be tight over a two-letter alphabet.     

Unit-free transformations of linear relativity

Linear relativistic transformations of special relativity considered in [A. Einstein, Zur Elektrodynamik der bewegter Körper, Ann. Phys. 17 (1905) 891–921] are analyzed and their representation through unit-free parameters is obtained in the form: $\tau /t=\xi /x^{\prime }=\gamma \left(p\right)={[1+{(p/V)}^2]}^{0.5}\in [1,\infty ),\eta /y=\zeta /z=1$, where $x^{\prime }=x?vt$, the relative velocity $v>0$ of a moving frame $\left(k\right)$ with respect to a still frame $\left(K\right)$ is constant and directed along $0x\in \left(K\right)$, the value $p=d\xi /dt=?\beta v=\text{const}$, with $\beta$ being the Einstein calibration factor, and the distance $\xi \left(t\right)$ to the origin of $\left(k\right)$, a moving body, is being measured by radar from a still point $x\in \left(K\right)$, on Earth, with respect to its natural time $t$. A new relativistic invariant is derived which admits trigonometric representation and can be extended onto nonlinear relativity with variable velocities. The unit-free form of relativistic transformations demonstrates that special relativity considerations are valid with respect to any available information transmitting signal, thus extending special relativity onto all interacting processes linked by such signals. Multi-relativistic situations are discussed in relation to the structure of observed time $\tau$. Natural time delays in transmission of information by physical processes are considered in relation to Minkowski’s 4D space–time geometry that becomes an affinely connected space–time structure with affinors being conditioned on the actually interacting physical processes. The results open new avenues for further research in relativity theory and its applications.     

On the definition of the intuitionistic fuzzy subgroups

In this paper, a new kind of intuitionistic fuzzy subgroup theory, which is different from that of Ma, Zhan and Davvaz (2008) [22], [23], is presented. First, based on the concept of cut sets on intuitionistic fuzzy sets, we establish the neighborhood relations between a fuzzy point $x_a$ and an intuitionistic fuzzy set $A$. Then we give the definitions of the grades of $x_a$ belonging to $A$, $x_a$ quasi-coincident with $A$, $x_a$ belonging to and quasi-coincident with $A$ and $x_a$ belonging to or quasi-coincident with $A$, respectively. Second, by applying the 3-valued Lukasiewicz implication, we give the definition of $(\alpha ,\beta )$-intuitionistic fuzzy subgroups of a group $G$ for $\alpha ,\beta \in \{\in ,q,\in \wedge q,\in \vee q\}$, and we show that, in 16 kinds of $(\alpha ,\beta )$-intuitionistic fuzzy subgroups, the significant ones are the $(\in ,\in )$-intuitionistic fuzzy subgroup, the $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup and the $(\in \wedge q,\in )$-intuitionistic fuzzy subgroup. We also show that $A$ is a $(\in ,\in )$-intuitionistic fuzzy subgroup of $G$ if and only if, for any $a\in (0,1]$, the cut set $A_a$ of $A$ is a 3-valued fuzzy subgroup of $G$, and $A$ is a $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup (or $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup) of $G$ if and only if, for any $a\in (0,0.5]$(or for any $a\in (0.5,1]$), the cut set $A_a$ of $A$ is a 3-valued fuzzy subgroup of $G$. At last, we generalize the $(\in ,\in )$-intuitionistic fuzzy subgroup, $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup and $(\in \wedge q,\in )$-intuitionistic fuzzy subgroup to intuitionistic fuzzy subgroups with thresholds, i.e., $(s,t]$-intuitionistic fuzzy subgroups. We show that $A$ is a $(s,t]$-intuitionistic fuzzy subgroup of $G$ if and only if, for any $a\in (s,t]$, the cut set $A_a$ of $A$ is a 3-valued fuzzy subgroup of $G$. We also characterize the $(s,t]$-intuitionistic fuzzy subgroup by the neighborhood relations between a fuzzy point $x_a$ and an intuitionistic fuzzy set $A$.     

Best uniform polynomial approximation of some rational functions

In this research paper using the Chebyshev expansion, we explicitly determine the best uniform polynomial approximation out of $P_{qn}$ (the space of polynomials of degree at most $qn$) to a class of rational functions of the form $1/(T_q\left(a\right)\pm T_q\left(x\right))$ on $[?1,1]$, where $T_q\left(x\right)$ is the first kind of Chebyshev polynomial of degree $q$ and $a^2>1$. In this way we give some new theorems about the best approximation of this class of rational functions. Furthermore we obtain the alternating set of this class of functions.     

Algebraic techniques for Schrödinger equations in split quaternionic mechanics

The split quaternionic Schrödinger equation $\frac{?}{?t}|f〉=?A|f〉$ plays an important role in split quaternionic mechanics, in which $A$ a split quaternion matrix. This paper, by means of a real representation of split quaternion matrices, studies problems of split quaternionic Schrödinger equation, and gives an algebraic technique for the split quaternionic Schrödinger equation. This paper also derives an algebraic technique for finding eigenvalues and eigenvectors of a split quaternion matrix in split quaternionic mechanics.     

Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph $G=(V,E)$ with edge-weights $w:E\to {\mathbb{R}}_{\ge 0}$ and vertex-weights $\eta :V\to {\mathbb{R}}_{+}$ are given. The goal is to find a vertex set $S\subseteq V$ with $|S|\le t$ while minimizing $w(S,V\backslash S)/\eta (S)$, where $w(S,V\backslash S)$ is the total weight of the edges with exactly one endpoint in S and $\eta (S)={\sum }_{v\in S}\eta (v)$. For this problem, we present a $(O(\log t),1+ϵ)$ factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when $t=n^{o(1)}$. We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.