An embedding theorem for regular Mal'tsev categories

In this paper, we obtain a non-abelian analogue of Lubkin's embedding theorem for abelian categories. Our theorem faithfully embeds any small regular Mal'tsev category $\mathbb{C}$ in an n-th power of a particular locally finitely presentable regular Mal'tsev category. The embedding preserves and reflects finite limits, isomorphisms and regular epimorphisms, as in the case of Barr's embedding theorem for regular categories. Furthermore, we show that we can take n to be the (cardinal) number of subobjects of the terminal object in $\mathbb{C}$.     

On functors preserving skeletal maps and skeletally generated compacta

A map $f:X\to Y$ between topological spaces is skeletal if the preimage $f^{?1}(A)$ of each nowhere dense subset $A?Y$ is nowhere dense in X. We prove that a normal functor $F:\mathbf{Comp}\to \mathbf{Comp}$ is skeletal (which means that F preserves skeletal epimorphisms) if and only if for any open surjective map $f:X\to Y$ between metrizable zero-dimensional compacta with two-element non-degeneracy set $N^f=\{x\in X:|f^{?1}(f(x))|>1\}$ the map $Ff:FX\to FY$ is skeletal. This characterization implies that each open normal functor is skeletal. The converse is not true even for normal functors of finite degree. The other main result of the paper says that each normal functor $F:\mathbf{Comp}\to \mathbf{Comp}$ preserves the class of skeletally generated compacta. This contrasts with the known ??epin?s result saying that a normal functor is open if and only if it preserves the class of openly generated compacta.     

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$.     

The Σ1-provability logic of HA

In this paper we introduce a modal theory ${\mathsf{iH}}_{\sigma }$ which is sound and complete for arithmetical ${\mathrm{\Sigma }}_1$-interpretations in $\mathsf{HA}$, in other words, we will show that ${\mathsf{iH}}_{\sigma }$ is the ${\mathrm{\Sigma }}_1$-provability logic of $\mathsf{HA}$. Moreover we will show that ${\mathsf{iH}}_{\sigma }$ is decidable. As a by-product of these results, we show that $\mathsf{HA}+\square \perp$ has de Jongh property.     

Constructing connected bicritical graphs with edge-connectivity 2

A graph $G$ is said to be bicritical if the removal of any pair of vertices decreases the domination number of $G$. For a bicritical graph $G$ with the domination number $t$, we say that $G$ is $t$-bicritical. Let $\lambda \left(G\right)$ denote the edge-connectivity of $G$. In [2], Brigham et al. (2005) posed the following question: If $G$ is a connected bicritical graph, is it true that $\lambda \left(G\right)\ge 3?$In this paper, we give a negative answer toward this question; namely, we give a construction of infinitely many connected $t$-bicritical graphs with edge-connectivity $2$ for every integer $t\ge 5$. Furthermore, we give some sufficient conditions for a connected $5$-bicritical graph to have $\lambda \left(G\right)\ge 3$.     

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 $?.$     

On the independence number of the power graph of a finite group

The power graph ${\Gamma }_G$ of a finite group $G$ is the graph whose vertex set is $G$, two distinct elements being adjacent if one is a power of the other. In this paper, we give sharp lower and upper bounds for the independence number of ${\Gamma }_G$ and characterize the groups achieving the bounds. Moreover, we determine the independence number of ${\Gamma }_G$ if $G$ is cyclic, dihedral or generalized quaternion. Finally, we classify all finite groups $G$ whose power graphs have independence number 3 or $n?2$, where $n$ is the order of $G$.     

Vertex-minimal graphs with dihedral symmetry I

Let $D_{2n}$ denote the dihedral group of order $2n$, where $n\ge 3$. In this article, we build upon the findings of Haggard and McCarthy who, for certain values of $n$, produced a vertex-minimal graph with dihedral symmetry. Specifically, Haggard considered the situation when $\frac{n}{2}$ or $n$ is a prime power, and McCarthy investigated the case when $n$ is not divisible by $2$, $3$ or $5$. In this article, we assume $n$ is not divisible by $4$ and construct a vertex-minimal graph whose automorphism group is isomorphic to $D_{2n}$.     

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.     

On left (right) ρ-transitive geometric spaces

In this article, first we generalize the concept of $\mathfrak{B}$-parts in a geometric space with respect to a binary relation $\rho$ and then we study left (right) $l{\mathfrak{B}}_{\rho }$-closures ($r{\mathfrak{B}}_{\rho }$-closures, respectively). Finally we introduce and investigate the notions left $\rho$-strongly transitive geometric spaces and left $\rho$-emphatic strongly transitive geometric spaces.     

Max-cut and extendability of matchings in distance-regular graphs

A connected graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is $1$-extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter $D\ge 3$ are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency $k\ge 3$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency $k$ grows linearly in $k$. We conjecture that the extendability of a distance-regular graph of even order and valency $k$ is at least $\lceil k/2\rceil -1$ and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters.     

Non-differentiability and Hölder properties of self-affine functions

We consider the class of self-affine functions. Firstly, we characterize all nowhere differentiable self-affine continuous functions. Secondly, given a self-affine continuous function $?$, we investigate its Hölder properties. We find its best uniform Hölder exponent and when $?$ is $C^1$, we find the best uniform Hölder exponent of ${?}^{\prime }$. Thirdly, we show that the Hölder cut of $?$ takes the same value almost everywhere for the Lebesgue measure. This last result is a consequence of the Borel strong law of large numbers.     

On k-domination and j-independence in graphs

Let $G$ be a graph and let $k$ and $j$ be positive integers. A subset $D$ of the vertex set of $G$ is a $k$-dominating set if every vertex not in $D$ has at least $k$ neighbors in $D$. The $k$-domination number ${\gamma }_k\left(G\right)$ is the cardinality of a smallest $k$-dominating set of $G$. A subset $I?V\left(G\right)$ is a $j$-independent set of $G$ if every vertex in $I$ has at most $j?1$ neighbors in $I$. The $j$-independence number ${\alpha }_j\left(G\right)$ is the cardinality of a largest $j$-independent set of $G$. In this work, we study the interaction between ${\gamma }_k\left(G\right)$ and ${\alpha }_j\left(G\right)$ in a graph $G$. Hereby, we generalize some known inequalities concerning these parameters and put into relation different known and new bounds on $k$-domination and $j$-independence. Finally, we will discuss several consequences that follow from the given relations, while always highlighting the symmetry that exists between these two graph invariants.     

Coverings: Variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl

We consider four problems. Rogers proved that for any convex body $K$, we can cover ${\mathbb{R}}^d$ by translates of $K$ of density very roughly $dlnd$. First, we extend this result by showing that, if we are given a family of positive homothets of $K$ of infinite total volume, then we can find appropriate translation vectors for each given homothet to cover ${\mathbb{R}}^d$ with the same (or, in certain cases, smaller) density.Second, we extend Rogers’ result to multiple coverings of space by translates of a convex body: we give a non-trivial upper bound on the density of the most economical covering where each point is covered by at least a certain number of translates.Third, we show that for any sufficiently large $n$, the sphere ${\mathbb{S}}^2$ can be covered by $n$ strips of width $20n∕lnn$, where no point is covered too many times.Finally, we give another proof of the previous result based on a combinatorial observation: an extension of the Epsilon-net Theorem of Haussler and Welzl. We show that for a hypergraph of bounded Vapnik–Chervonenkis dimension, in which each edge is of a certain measure, there is a not-too large transversal set which does not intersect any edge too many times.     

Counting arithmetical structures on paths and cycles

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(diag\left(\mathbf{d}\right)?A)\mathbf{r}=0$, where $A$ is the adjacency matrix of $G$. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices $(diag\left(\mathbf{d}\right)?A)$). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\left(\genfrac{}{}{0ex}{}{2n?1}{n?1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.