Search results for "Conjecture"

Some properties of vertex-oblique graphs

2016

The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…

Unconditionally convergent multipliers and Bessel sequences

2016

Abstract We prove that every unconditionally summable sequence in a Hilbert space can be factorized as the product of a square summable scalar sequence and a Bessel sequence. Some consequences on the representation of unconditionally convergent multipliers are obtained, thus providing positive answers to a conjecture by Balazs and Stoeva in some particular cases.

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture

2005

A language L over an alphabet A is said to have a neutral letter if there is a letter [email protected]?A such that inserting or deleting e's from any word in A^* does not change its membership or non-membership in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order, then it is not definable in first-order logic with any set N of numerical predicates. Named after the location of its first, flawed, proof this conjecture is called the Crane Beach …

On a Conjecture on Bidimensional Words

2003

We prove that, given a double sequence w over the alphabet A (i.e. a mapping from Z2 to A), if there exists a pair (n0, m0) ∈ Z2 such that pw(n0, m0) < 1/100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.

The real cubic case of Mahler's conjecture

1961

Real groups and Sylow 2-subgroups

2016

Abstract If G is a finite real group and P ∈ Syl 2 ( G ) , then P / P ′ is elementary abelian. This confirms a conjecture of Roderick Gow. In fact, we prove a much stronger result that implies Gow's conjecture.

The branch set of a quasiregular mapping between metric manifolds

2016

Abstract In this note, we announce some new results on quantitative countable porosity of the branch set of a quasiregular mapping in very general metric spaces. As applications, we solve a recent conjecture of Fassler et al., an open problem of Heinonen–Rickman, and an open question of Heinonen–Semmes.

Recognizable picture languages and polyominoes

2007

We consider the problem of recognizability of some classes of polyominoes in the theory of picture languages. In particular we focus our attention oil the problem posed by Matz of finding a non-recognizable picture language for which his technique for proving the non-recognizability of picture languages fails. We face the problem by studying the family of L-convex polyominoes and some closed families that are similar to the recognizable family of all polyominoes but result to be non-recognizable. Furthermore we prove that the family of L-convex polyominoes satisfies the necessary condition given by Matz for the recognizability and we conjecture that the family of L-convex polyominoes is non…

Sturmian Graphs and a conjecture of Moser

2004

In this paper we define Sturmian graphs and we prove that all of them have a “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words, these graphs converge to infinite ones.

On the Power of Tree-Walking Automata

2000

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class …