Contraction of cyclic codes over finite chain rings

In this paper, $R$ is a finite chain ring with residue field ${\mathbb{F}}_q$ and $\gamma$ is a unit in $R.$ By assuming that the multiplicative order $u$ of $\gamma$ is coprime to $q,$ we give the trace-representation of any simple-root $\gamma$-constacyclic code over $R$ of length $?,$ and on the other hand show that any cyclic code over $R$ of length $u?$ is a direct sum of trace-representable cyclic codes. Finally, we characterize the simple-root, contractable and cyclic codes over $R$ of length $u?$ into $\gamma$-constacyclic codes of length $?.$     

Group-labeled light dual multinets in the projective plane

In this paper we investigate light dual multinets labeled by a finite group in the projective plane $PG(2,\mathbb{K})$ defined over a field $\mathbb{K}$. We present two classes of new examples. Moreover, under some conditions on the characteristic of $\mathbb{K}$, we classify group-labeled light dual multinets with lines of length at least 9.     

Descent distribution on Catalan words avoiding a pattern of length at most three

Catalan words are particular growth-restricted words over the set of non-negative integers, and they represent still another combinatorial class counted by the Catalan numbers. We study the distribution of descents on the sets of Catalan words avoiding a pattern of length at most three: for each such a pattern $p$ we provide a bivariate generating function where the coefficient of $x^n{y}^k$ in its series expansion is the number of length $n$$p$-avoiding Catalan words with $k$ descents. As a byproduct, we enumerate the set of Catalan words avoiding $p$, and we provide the popularity of descents on this set.     

Copositive and semidefinite relaxations of the quadratic assignment problem

Semidefinite relaxations of the quadratic assignment problem ($QAP$) have recently turned out to provide good approximations to the optimal value of $QAP$. We take a systematic look at various conic relaxations of $QAP$. We first show that $QAP$ can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it is hard to optimize over this cone, we also look at tractable approximations and compare with several relaxations from the literature. We show that several of the well-studied models are in fact equivalent. It is still a challenging task to solve the strongest of these models to reasonable accuracy on instances of moderate size.     

The odd primary homology of SU(n), Sp(n) and Spin(n)-gauge groups

For an odd prime $p$, we calculate the mod-$p$ homology of $SU\left(n\right)$-gauge groups over a simply-connected, closed 4-manifold for all $n\ge 2$. Similar calculations are obtained for the structure groups $Sp\left(n\right)$ when $n\ge 1$ and $Spin\left(n\right)$ for $n\ge 3$ (except for some cases when $n$ is even and $p=3$).     

What does a group algebra of a free group “know” about the group?

We describe solutions to the problem of elementary classification in the class of group algebras of free groups. We will show that unlike free groups, two group algebras of free groups over infinite fields are elementarily equivalent if and only if the groups are isomorphic and the fields are equivalent in the weak second order logic. We will show that the set of all free bases of a free group F is 0-definable in the group algebra $K(F)$ when K is an infinite field, the set of geodesics is definable, and many geometric properties of F are definable in $K(F)$. Therefore $K(F)$ “knows” some very important information about F. We will show that similar results hold for group algebras of limit groups.     

The perimeter of words

We define $\left[k\right]=\{1,2,\dots ,k\}$ to be a (totally ordered) alphabet on $k$ letters. A word $w$ of length $n$ on the alphabet $\left[k\right]$ is an element of ${\left[k\right]}^n$. A word can be represented by a bargraph (i.e., by a column-convex polyomino whose lower edges lie on the $x$-axis) in which the height of the $i$th column equals the size of the $i$th part of the word. Thus these bargraphs have heights which are less than or equal to $k$. We consider the perimeter, which is the number of edges on the boundary of the bargraph. By way of Cramer’s method and the kernel method, we obtain the generating function that counts the perimeter of words. Using these generating functions we find the average perimeter of words of length $n$ over the alphabet $\left[k\right]$. We also show how the mean and variance can be obtained using a direct counting method.     

Mutually describing multisets and integer partitions

To each finite multiset $A$, with underlying set $S\left(A\right)$, we associate a new multiset $d\left(A\right)$, obtained by adjoining to $S\left(A\right)$ the multiplicities of its elements in $A$. We study the orbits of the map $d$ under iteration, and show that if $A$ consists of nonnegative integers, then its orbit under $d$ converges to a cycle. Moreover, we prove that all cycles of $d$ over $\mathbb{Z}$ are of length at most $3$, and we completely determine them. This amounts to finding all systems of mutually describing multisets. In the process, we are led to introduce and study a related discrete dynamical system on the set of integer partitions of $n$ for each $n\ge 1$.     

Histories in Path Graphs

For a given graph G and a positive integer r the r-path graph, $P_r(G)$, has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length $r-1$, and their union forms either a cycle or a path of length $r+1$ in G. Let $P_r^k(G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_r^k(G)$. The k-history $P_r^{-k}(H)$ is a subgraph of G that is induced by all edges that take part in the recursive definition of H. We present some general properties of k-histories and give a complete characterization of graphs that are k-histories of vertices of 2-path graph operator.     

Fixed points of n-valued maps,the fixed point property and the case of surfaces—A braid approach

We study the fixed point theory of $n$-valued maps of a space $X$ using the fixed point theory of maps between $X$ and its configuration spaces. We give some general results to decide whether an $n$-valued map can be deformed to a fixed point free $n$-valued map. In the case of surfaces, we provide an algebraic criterion in terms of the braid groups of $X$ to study this problem. If $X$ is either the $k$-dimensional ball or an even-dimensional real or complex projective space, we show that the fixed point property holds for $n$-valued maps for all $n\ge 1$, and we prove the same result for even-dimensional spheres for all $n\ge 2$. If $X$ is the $2$-torus, we classify the homotopy classes of $2$-valued maps in terms of the braid groups of $X$. We do not currently have a complete characterisation of the homotopy classes of split $2$-valued maps of the $2$-torus that contain a fixed point free representative, but we give an infinite family of such homotopy classes.     

Locating a robber with multiple probes

We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager (2012). Carragher, Choi, Delcourt, Erickson and West showed that for any $n$-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1∕m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m\ge n$ (Carragher et al., 2012). The present authors showed that, for all but a few small values of $n$, this bound may be improved to $m\ge n∕2$, which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph with the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $\Delta$, which is best possible up to a factor of $(1?o\left(1\right))$.