Currently displaying 1 – 8 of 8

Showing per page

Order by Relevance | Title | Year of publication

Hereditary properties of words

József BaloghBéla Bollobás — 2005

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Let 𝒫 be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to 𝒫 is also in 𝒫 . Extending the classical Morse-Hedlund theorem, we show that either 𝒫 contains at least n + 1 words of length n for every n or, for some N , it contains at most N words of length n for every n . More importantly, we prove the following quantitative extension of this result: if 𝒫 has m n words of length n then, for every k n + m , it contains at most ( m + 1 ) / 2 ( m + 1 ) / 2 words of length...

Hereditary properties of words

József BaloghBéla Bollobás — 2010

RAIRO - Theoretical Informatics and Applications

Let be a hereditary property of words, , an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every  or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most ⌈( + 1)/2⌉⌈( + 1)/2⌈ words of...

Coloring Some Finite Sets in ℝn

József BaloghAlexandr KostochkaAndrei Raigorodskii — 2013

Discussiones Mathematicae Graph Theory

This note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of...

Complete minors, independent sets, and chordal graphs

József BaloghJohn LenzHehui Wu — 2011

Discussiones Mathematicae Graph Theory

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.

Page 1

Download Results (CSV)