اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTight Lower Bound for Average Number of Terms in Optimal Double-base Number System
63
0
0.0
(
0
)
نشر من قبل
Vorapong Suppakitpaisarn
تاريخ النشر
2021
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
تأليف
Vorapong Suppakitpaisarn
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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).
قيم البحث
اقرأ أيضاً
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph $G$ contains a cactus subgraph $C$ where $C$ contains at least a $frac{1}{6}$ fraction of the triangular faces of $G
$. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing dense planar structures inside any graph: (i) A $frac{1}{6}$ approximation algorithm for, given any graph $G$, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous $frac{1}{11}$-approximation; (ii) An alternate (and arguably more illustrative) proof of the $frac{4}{9}$ approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.
The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers $ngeq Dgeq 1$, there exists a port-labeled network with at most $n$ nodes and diameter at mo
st $D$ which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth $Omega(Dlog (n/D))$ are identical.
In [13] the authors show that if $mu$ is a strongly compact cardinal, $K$ is an Abstract Elementary Class (AEC) with $LS(K)<mu$, and $K$ satisfies joint embedding (amalgamation) cofinally below $mu$, then $K$ satisfies joint embedding (amalgamation)
in all cardinals $ge mu$. The question was raised if the strongly compact upper bound was optimal. In this paper we prove the existence of an AEC $K$ that can be axiomatized by an $mathcal{L}_{omega_1,omega}$-sentence in a countable vocabulary, so that if $mu$ is the first measurable cardinal, then (1) $K$ satisfies joint embedding cofinally below $mu$ ; (2) $K$ fails joint embedding cofinally below $mu$; and (3) $K$ satisfies joint embedding above $mu$. Moreover, the example can be generalized to an AEC $K^chi$ axiomatized in $mathcal{L}_{chi^+, omega}$, in a vocabulary of size $chi$, such that (1)-(3) hold with $mu$ being the first measurable above $chi$. This proves that the Hanf number for joint embedding is contained in the interval between the first measurable and the first strongly compact. Since these two cardinals can consistently coincide, the upper bound from [13] is consistently optimal. This is also the first example of a sentence whose joint embedding spectrum is (consistently) neither an initial nor an eventual interval of cardinals. By Theorem 3.26, it is consistent that for any club $C$ on the first measurable $mu$, JEP holds exactly on $lim C$ and everywhere above $mu$.
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.
An interval edge t-coloring of a graph G is a proper edge coloring of G with colors 1,2...,t such that at least one edge of G is colored by color i,i=1,2...,t, and the edges incident with each vertex v are colored by d_{G}(v) consecutive colors, wher
e d_{G}(v) is the degree of the vertex v in G. In this paper interval edge colorings of bipartite cylinders and bipartite tori are investigated.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
