Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCounting number of factorizations of a natural number
143
0
0.0
(
0
)
Added by
Shamik Ghosh
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Shamik Ghosh
Ask ChatGPT about the research
No Arabic abstract
In this note we describe a new method of counting the number of unordered factorizations of a natural number by means of a generating function and a recurrence relation arising from it, which improves an earlier result in this direction.
rate research
Read More
We show in this note that the average number of terms in the optimal double-base number system is in Omega(n / log n). The lower bound matches the upper bound shown earlier by Dimitrov, Imbert, and Mishra (Math. of Comp. 2008).
The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n-1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G|-1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n >= 10, there are graphs on n vertices on which Colour Refinement requires at least n-2 iterations to reach stabilisation.
The combinatorics of squares in a word depends on how the equivalence of halves of the square is defined. We consider Abelian squares, parameterized squares, and order-preserving squares. The word $uv$ is an Abelian (parameterized, order-preserving) square if $u$ and $v$ are equivalent in the Abelian (parameterized, order-preserving) sense. The maximum number of ordinary squares in a word is known to be asymptotically linear, but the exact bound is still investigated. We present several results on the maximum number of distinct squares for nonstandard subword equivalence relations. Let $mathit{SQ}_{mathrm{Abel}}(n,sigma)$ and $mathit{SQ}_{mathrm{Abel}}(n,sigma)$ denote the maximum number of Abelian squares in a word of length $n$ over an alphabet of size $sigma$, which are distinct as words and which are nonequivalent in the Abelian sense, respectively. For $sigmage 2$ we prove that $mathit{SQ}_{mathrm{Abel}}(n,sigma)=Theta(n^2)$, $mathit{SQ}_{mathrm{Abel}}(n,sigma)=Omega(n^{3/2})$ and $mathit{SQ}_{mathrm{Abel}}(n,sigma) = O(n^{11/6})$. We also give linear bounds for parameterized and order-preserving squares for alphabets of constant size: $mathit{SQ}_{mathrm{param}}(n,O(1))=Theta(n)$, $mathit{SQ}_{mathrm{op}}(n,O(1))=Theta(n)$. The upper bounds have quadratic dependence on the alphabet size for order-preserving squares and exponential dependence for parameterized squares. As a side result we construct infinite words over the smallest alphabet which avoid nontrivial order-preserving squares and nontrivial parameterized cubes (nontrivial parameterized squares cannot be avoided in an infinite word).
Let X be a projective curve over Q and t a non-constant Q-rational function on X of degree n>1. For every integer a pick a points P(a) on X such that t(P(a))=a. Dvornicich and Zannier (1994) proved that for large N the field Q(P(1), ..., P(N)) is of degree at least exp(cN/log N) over Q, where c>0 depends only on X and t. In this note we extend this result, replacing Q by an arbitrary number field.
An $(m, n)$-colored mixed graph is a graph having arcs of $m$ different colors and edges of $n$ different colors. A graph homomorphism of an $(m, n$)-colored mixed graph $G$ to an $(m, n)$-colored mixed graph $H$ is a vertex mapping such that if $uv$ is an arc (edge) of color $c$ in $G$, then $f(u)f(v)$ is also an arc (edge) of color $c$. The ($m, n)$-colored mixed chromatic number of an $(m, n)$-colored mixed graph $G$, introduced by Nev{s}etv{r}il and Raspaud [J. Combin. Theory Ser. B 2000] is the order (number of vertices) of the smallest homomorphic image of $G$. Later Bensmail, Duffy and Sen [Graphs Combin. 2017] introduced another parameter related to the $(m, n)$-colored mixed chromatic number, namely, the $(m, n)$-relative clique number as the maximum cardinality of a vertex subset which, pairwise, must have distinct images with respect to any colored homomorphism. In this article, we study the $(m, n$)-relative clique number for the family of subcubic graphs, graphs with maximum degree $Delta$, planar graphs and triangle-free planar graphs and provide new improved bounds in each of the cases. In particular, for subcubic graphs we provide exact value of the parameter.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
