Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the number of words with restrictions on the number of symbols
224
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that, in an alphabet of $n$ symbols, the number of words of length $n$ whose number of different symbols is away from $(1-1/e)n$, which is the value expected by the Poisson distribution, has exponential decay in $n$. We use Laplaces method for sums and known bounds of Stirling numbers of the second kind. We express our result in terms of inequalities.
rate research
Read More
Let $G_{1}$ and $G_{2}$ be disjoint copies of a graph $G$, and let $g:V(G_{1})rightarrow V(G_{2})$ be a function. A functigraph $F_{G}$ consists of the vertex set $V(G_{1})cup V(G_{2})$ and the edge set $E(G_{1})cup E(G_{2})cup {uv:g(u)=v}$. In this paper, we extend the study of the distinguishing number of a graph to its functigraph. We discuss the behavior of the distinguishing number in passing from $G$ to $F_{G}$ and find its sharp lower and upper bounds. We also discuss the distinguishing number of functigraphs of complete graphs and join graphs.
The fixing number of a graph $G$ is the smallest cardinality of a set of vertices $Fsubseteq V(G)$ such that only the trivial automorphism of $G$ fixes every vertex in $F$. Let $Pi$ $=$ ${F_1,F_2,ldots,F_k}$ be an ordered $k$-partition of $V(G)$. Then $Pi$ is called a {it fixatic partition} if for all $i$; $1leq ileq k$, $F_i$ is a fixing set for $G$. The cardinality of a largest fixatic partition is called the {it fixatic number} of $G$. In this paper, we study the fixatic numbers of graphs. Sharp bounds for the fixatic number of graphs in general and exact values with specified conditions are given. Some realizable results are also given in this paper.
In this paper, we give bounds on the dichromatic number $vec{chi}(Sigma)$ of a surface $Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $Sigma$. We determine the asymptotic behaviour of $vec{chi}(Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1frac{sqrt{-c}}{log(-c)} leq vec{chi}(Sigma) leq a_2 frac{sqrt{-c}}{log(-c)} $ for every surface $Sigma$ with Euler characteristic $cleq -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $mathbb{N}_1$, the Klein bottle $mathbb{N}_2$, the torus $mathbb{S}_1$, and Dycks surface $mathbb{N}_3$ are all equal to $3$, and that the dichromatic numbers of the $5$-torus $mathbb{S}_5$ and the $10$-cross surface $mathbb{N}_{10}$ are equal to $4$. We also consider the complexity of deciding whether a given digraph or oriented graph embedabble in a fixed surface is $k$-dicolourable. In particular, we show that for any surface, deciding whether a digraph embeddable on this surface is $2$-dicolourable is NP-complete, and that deciding whether a planar oriented graph is $2$-dicolourable is NP-complete unless all planar oriented graphs are $2$-dicolourable (which was conjectured by Neumann-Lara).
We determine the asymptotic behaviour of the chromatic number of exchangeable random graphs defined by step-regulated graphons. Furthermore, we show that the upper bound holds for a general graphon. We also extend these results to sparse random graphs obtained by percolations on graphons.
The number of planar Eulerian maps with n edges is well-known to have a simple expression. But what is the number of planar Eulerian orientations with n edges? This problem appears to be difficult. To approach it, we define and count families of subsets and supersets of planar Eulerian orientations, indexed by an integer k, that converge to the set of all planar Eulerian orientations as k increases. The generating functions of our subsets can be characterized by systems of polynomial equations, and are thus algebraic. The generating functions of our supersets are characterized by polynomial systems involving divided differences, as often occurs in map enumeration. We prove that these series are algebraic as well. We obtain in this way lower and upper bounds on the growth rate of planar Eulerian orientations, which appears to be around 12.5.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
