No Arabic abstract
In this paper, we consider the possible types of regular maps of order $2^n$, where the order of a regular map is the order of automorphism group of the map. For $n le 11$, M. Conder classified all regular maps of order $2^n$. It is easy to classify regular maps of order $2^n$ whose valency or covalency is $2$ or $2^{n-1}$. So we assume that $n geq 12$ and $2leq s,tleq n-2$ with $sleq t$ to consider regular maps of order $2^n$ with type ${2^s, 2^t}$. We show that for $s+tleq n$ or for $s+t>n$ with $s=t$, there exists a regular map of order $2^n$ with type ${2^s, 2^t}$, and furthermore, we classify regular maps of order $2^n$ with types ${2^{n-2},2^{n-2}}$ and ${2^{n-3},2^{n-3}}$. We conjecture that, if $s+t>n$ with $s<t$, then there is no regular map of order $2^n$ with type ${2^s, 2^t}$, and we confirm the conjecture for $t=n-2$ and $n-3$.
A permutation $sigma$ describing the relative orders of the first $n$ iterates of a point $x$ under a self-map $f$ of the interval $I=[0,1]$ is called an emph{order pattern}. For fixed $f$ and $n$, measuring the points $xin I$ (according to Lebesgue measure) that generate the order pattern $sigma$ gives a probability distribution $mu_n(f)$ on the set of length $n$ permutations. We study the distributions that arise this way for various classes of functions $f$. Our main results treat the class of measure preserving functions. We obtain an exact description of the set of realizable distributions in this case: for each $n$ this set is a union of open faces of the polytope of flows on a certain digraph, and a simple combinatorial criterion determines which faces are included. We also show that for general $f$, apart from an obvious compatibility condition, there is no restriction on the sequence ${mu_n(f)}$ for $n=1,2,...$. In addition, we give a necessary condition for $f$ to have emph{finite exclusion type}, i.e., for there to be finitely many order patterns that generate all order patterns not realized by $f$. Using entropy we show that if $f$ is piecewise continuous, piecewise monotone, and either ergodic or with points of arbitrarily high period, then $f$ cannot have finite exclusion type. This generalizes results of S. Elizalde.
A graph is $ell$-reconstructible if it is determined by its multiset of induced subgraphs obtained by deleting $ell$ vertices. We prove that $3$-regular graphs are $2$-reconstructible.
Let $p_{k,3}(n)$ enumerate the number of 2-color partition triples of $n$ where one of the colors appears only in parts that are multiples of $k$. In this paper, we prove several infinite families of congruences modulo powers of 3 for $p_{k,3}(n)$ with $k=1, 3$, and $9$. For example, for all integers $ngeq0$ and $alphageq1$, we prove that begin{align*} p_{3,3}left(3^{alpha}n+dfrac{3^{alpha}+1}{2}right) &equiv0pmod{3^{alpha+1}} end{align*} and begin{align*} p_{3,3}left(3^{alpha+1}n+dfrac{5times3^{alpha}+1}{2}right) &equiv0pmod{3^{alpha+4}}. end{align*}
A two-dimensional simplicial complex is called $d$-{em regular} if every edge of it is contained in exactly $d$ distinct triangles. It is called $epsilon$-expanding if its up-down two-dimensional random walk has a normalized maximal eigenvalue which is at most $1-epsilon$. In this work, we present a class of bounded degree 2-dimensional expanders, which is the result of a small 2-complex action on a vertex set. The resulted complexes are fully transitive, meaning the automorphism group acts transitively on their faces. Such two-dimensional expanders are rare! Known constructions of such bounded degree two-dimensional expander families are obtained from deep algebraic reasonings (e.g. coset geometries). We show that given a small $d$-regular two-dimensional $epsilon$-expander, there exists an $epsilon=epsilon(epsilon)$ and a family of bounded degree two-dimensional simplicial complexes with a number of vertices goes to infinity, such that each complex in the family satisfies the following properties: * It is $4d$-regular. * The link of each vertex in the complex is the same regular graph (up to isomorphism). * It is $epsilon$ expanding. * It is transitive. The family of expanders that we get is explicit if the one-skeleton of the small complex is a complete multipartite graph, and it is random in the case of (almost) general $d$-regular complex. For the randomized construction, we use results on expanding generators in a product of simple Lie groups. This construction is inspired by ideas that occur in the zig-zag product for graphs. It can be seen as a loose two-dimensional analog of the replacement product.
In this article we have derived the minimum order of an odd regular graph such that the graph has no matching. We have observed that how it is different from the case of even regular graphs. We have checked the consistency of the derived result with Petersens theorem.