Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight Lower Bound for Average Number of Terms in Optimal Double-base Number System
63
0
0.0
(
0
)
Added by
Vorapong Suppakitpaisarn
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Vorapong Suppakitpaisarn
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
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 most $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, where 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
