Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNo extremal square-free words over large alphabets
84
0
0.0
(
0
)
Added by
Shengtong Zhang
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A word is square-free if it does not contain any square (a word of the form $XX$), and is extremal square-free if it cannot be extended to a new square-free word by inserting a single letter at any position. Grytczuk, Kordulewski, and Niewiadomski proved that there exist infinitely many ternary extremal square-free words. We establish that there are no extremal square-free words over any alphabet of size at least 17.
rate research
Read More
Chen, Kitaev, M{u}tze, and Sun recently introduced the notion of universal partial words, a generalization of universal words and de Bruijn sequences. Universal partial words allow for a wild-card character $diamond$, which is a placeholder for any letter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic $diamond$ structure and are cyclic, and we give number-theoretic conditions on the existence of universal partial words. In addition, we provide an explicit construction for a family of universal partial words over alphabets of even size.
For positive integers $w$ and $k$, two vectors $A$ and $B$ from $mathbb{Z}^w$ are called $k$-crossing if there are two coordinates $i$ and $j$ such that $A[i]-B[i]geq k$ and $B[j]-A[j]geq k$. What is the maximum size of a family of pairwise $1$-crossing and pairwise non-$k$-crossing vectors in $mathbb{Z}^w$? We state a conjecture that the answer is $k^{w-1}$. We prove the conjecture for $wleq 3$ and provide weaker upper bounds for $wgeq 4$. Also, for all $k$ and $w$, we construct several quite different examples of families of desired size $k^{w-1}$. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.
Given a graph $H$, a graph is $H$-free if it does not contain $H$ as a subgraph. We continue to study the topic of extremal planar graphs, that is, how many edges can an $H$-free planar graph on $n$ vertices have? We define $ex_{_mathcal{P}}(n,H)$ to be the maximum number of edges in an $H$-free planar graph on $n $ vertices. We first obtain several sufficient conditions on $H$ which yield $ex_{_mathcal{P}}(n,H)=3n-6$ for all $nge |V(H)|$. We discover that the chromatic number of $H$ does not play a role, as in the celebrated ErdH{o}s-Stone Theorem. We then completely determine $ex_{_mathcal{P}}(n,H)$ when $H$ is a wheel or a star. Finally, we examine the case when $H$ is a $(t, r)$-fan, that is, $H$ is isomorphic to $K_1+tK_{r-1}$, where $tge2$ and $rge 3$ are integers. However, determining $ex_{_mathcal{P}}(n,H)$, when $H$ is a planar subcubic graph, remains wide open.
An extension of the well-known Szeged index was introduced recently, named as weighted Szeged index ($textrm{sz}(G)$). This paper is devoted to characterizing the extremal trees and graphs of this new topological invariant. In particular, we proved that the star is a tree having the maximal $textrm{sz}(G)$. Finding a tree with the minimal $textrm{sz}(G)$ is not an easy task to be done. Here, we present the minimal trees up to 25 vertices obtained by computer and describe the regularities which retain in them. Our preliminary computer tests suggest that a tree with the minimal $textrm{sz}(G)$ is also the connected graph of the given order that attains the minimal weighted Szeged index. Additionally, it is proven that among the bipartite connected graphs the complete balanced bipartite graph $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ attains the maximal $textrm{sz}(G)$,. We believe that the $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ is a connected graph of given order that attains the maximum $textrm{sz}(G)$.
We present results on the existence of long arithmetic progressions in the Thue-Morse word and in a class of generalised Thue-Morse words. Our arguments are inspired by van der Waerdens proof for the existence of arbitrary long monochromatic arithmetic progressions in any finite colouring of the (positive) integers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
