Unique factorisation of additive induced-hereditary properties

Alastair Farrugia; R. Bruce Richter

Displaying similar documents to “Unique factorisation of additive induced-hereditary properties”

Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

Ewa Drgas-Burchardt (2009)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^{a}$ denote a class of all such properties. In the paper, we consider H-reducible over $L^{a}$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

A note on joins of additive hereditary graph properties

Ewa Drgas-Burchardt (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Let $L^{a}$ denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set $(L^{a}, \subseteq)$ is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in $(L^{a}, \subseteq)$ has a finite or infinite family of minimal forbidden subgraphs.

Graphs with small additive stretch number

Dieter Rautenbach (2004)

Discussiones Mathematicae Graph Theory

Similarity:

The additive stretch number $s_{a d d} (G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{a d d} (G) \leq k$ for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

On Meager Additive and Null Additive Sets in the Cantor Space $2^{ω}$ and in ℝ

Tomasz Weiss (2009)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

Let T be the standard Cantor-Lebesgue function that maps the Cantor space $2^{ω}$ onto the unit interval ⟨0,1⟩. We prove within ZFC that for every $X \subseteq 2^{ω}$ , X is meager additive in $2^{ω}$ iff T(X) is meager additive in ⟨0,1⟩. As a consequence, we deduce that the cartesian product of meager additive sets in ℝ remains meager additive in ℝ × ℝ. In this note, we also study the relationship between null additive sets in $2^{ω}$ and ℝ.

On the completeness of decomposable properties of graphs

Mariusz Hałuszczak, Pavol Vateha (1999)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G [E_{i}]$ has the property $_{i}$ , i = 1,2. Let us define a property ₁⊕₂ by G: G has a (₁,₂)-decomposition. A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties...

Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

Izak Broere, Jozef Bucko, Peter Mihók (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,₂,...,ₙ be graph properties, a graph G is said to be uniquely (₁,₂, ...,ₙ)-partitionable if there is exactly one (unordered) partition V₁,V₂,...,Vₙ of V(G) such that $G [V_{i}] \in_{i}$ for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (₁,₂,...,ₙ)-partitionable graphs exist if and only if $_{i}$ and $_{j}$ are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ 1,2,...,n.

Addendum to “On Meager Additive and Null Additive Sets in the Cantor space $2^{ω}$ and in ℝ” (Bull. Polish Acad. Sci. Math. 57 (2009), 91-99)

Tomasz Weiss (2014)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

We prove in ZFC that there is a set $A \subseteq 2^{ω}$ and a surjective function H: A → ⟨0,1⟩ such that for every null additive set X ⊆ ⟨0,1), $H^{- 1} (X)$ is null additive in $2^{ω}$ . This settles in the affirmative a question of T. Bartoszyński.

Minimal forbidden subgraphs of reducible graph properties

Amelie J. Berger (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is any class of graphs closed under isomorphism. Let ₁,₂,...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable if the vertex set V(G) can be partitioned into n sets, V₁,V₂,..., Vₙ, such that for each i = 1,2,...,n, the graph $G [V_{i}] \in_{i}$ . We write ₁∘₂∘...∘ₙ for the property of all graphs which have a (₁,₂,...,ₙ)-partition. An additive induced-hereditary property is called reducible if there exist additive induced-hereditary properties ₁ and ₂ such that = ₁∘₂....

Acyclic reducible bounds for outerplanar graphs

Mieczysław Borowiecki, Anna Fiedorowicz, Mariusz Hałuszczak (2009)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. $G [V_{i}] \in_{i}$ for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that $u \in V_{i}$ and $v \in V_{j}$ is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring....

Uniquely partitionable graphs

Jozef Bucko, Marietjie Frick, Peter Mihók, Roman Vasky (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G [V_{i}]$ induced by $V_{i}$ has property $_{i}$ ; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property...

The decomposability of additive hereditary properties of graphs

Izak Broere, Michael J. Dorfling (2000)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that $G [E_{i}]$ , the subgraph of G induced by $E_{i}$ , is in $_{i}$ , for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such...

On the concentration of certain additive functions

Dimitris Koukoulopoulos (2014)

Acta Arithmetica

Similarity:

We study the concentration of the distribution of an additive function f when the sequence of prime values of f decays fast and has good spacing properties. In particular, we prove a conjecture by Erdős and Kátai on the concentration of $f (n) = \sum_{p | n} {(l o g p)}^{- c}$ when c > 1.

Sums of reciprocals of additive functions running over short intervals

J.-M. De Koninck, I. Kátai (2007)

Colloquium Mathematicae

Similarity:

Letting f(n) = A log n + t(n), where t(n) is a small additive function and A a positive constant, we obtain estimates for the quantities $\sum_{x \leq n \leq x + H} 1 / f (Q (n))$ and $\sum_{x \leq p \leq x + H} 1 / f (Q (p))$ , where H = H(x) satisfies certain growth conditions, p runs over prime numbers and Q is a polynomial with integer coefficients, whose leading coefficient is positive, and with all its roots simple.

Generalized chromatic numbers and additive hereditary properties of graphs

Izak Broere, Samantha Dorfling, Elizabeth Jonck (2002)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be additive hereditary properties of graphs. The generalized chromatic number $χ_{} ()$ is defined as follows: $χ_{} () = n$ iff ⊆ ⁿ but $⊊^{n - 1}$ . We investigate the generalized chromatic numbers of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ and ₖ.

On Vitali-Hahn-Saks-Nikodym type theorems

Barbara T. Faires (1976)

Annales de l'institut Fourier

Similarity:

A Boolean algebra $𝒜$ has the interpolation property (property (I)) if given sequences $(a_{n})$ , $(b_{m})$ in $𝒜$ with $a_{n} \leq b_{m}$ for all $n, m$ , there exists an element $b$ in $𝒜$ such that $a_{n} \leq b \leq b_{n}$ for all $n$ . Let $𝒜$ denote an algebra with the property (I). It is shown that if $(μ_{n} : 𝒜 \to X)$ ( $X$ a Banach space) is a sequence of strongly additive measures such that ${lim}_{n} μ_{n} (a)$ exists for each $a \in 𝒜$ , then $μ (a) = {lim}_{n} μ_{n} (a)$ defines a strongly additive map from $𝒜$ to $X$ the $μ_{n}^{'} s$ are uniformly strongly additive. The Vitali-Hahn-Saks (VHS) theorem for strongly additive...

On a conjecture of Sárközy and Szemerédi

Yong-Gao Chen (2015)

Acta Arithmetica

Similarity:

Two infinite sequences A and B of non-negative integers are called infinite additive complements if their sum contains all sufficiently large integers. In 1994, Sárközy and Szemerédi conjectured that there exist infinite additive complements A and B with lim sup A(x)B(x)/x ≤ 1 and A(x)B(x)-x = O(minA(x),B(x)), where A(x) and B(x) are the counting functions of A and B, respectively. We prove that, for infinite additive complements A and B, if lim sup A(x)B(x)/x ≤ 1, then, for any given...

A remark on E. Green’s paper “Completeness of $L^{p}$ -spaces over finitely additive set functions”

K. P. S. Bhaskara Rao, Vincenzo Aversa (1987)

Colloquium Mathematicae

Similarity:

Completeness of $L^{p}$ -spaces over finitely additive set functions

Euline Green (1971)

Colloquium Mathematicae

Similarity:

$F_{σ}$ -additive covers of Čech complete and scattered-K-analytic spaces

Jiří Spurný (2008)

Fundamenta Mathematicae

Similarity:

We prove that an $F_{σ}$ -additive cover of a Čech complete, or more generally scattered-K-analytic space, has a σ-scattered refinement. This generalizes results of G. Koumoullis and R. W. Hansell.

A note on the super-additive and sub-additive transformations of aggregation functions: The multi-dimensional case

Fateme Kouchakinejad, Alexandra Šipošová (2017)

Kybernetika

Similarity:

For an aggregation function $A$ we know that it is bounded by $A^{*}$ and $A_{*}$ which are its super-additive and sub-additive transformations, respectively. Also, it is known that if $A^{*}$ is directionally convex, then $A = A^{*}$ and $A_{*}$ is linear; similarly, if $A_{*}$ is directionally concave, then $A = A_{*}$ and $A^{*}$ is linear. We generalize these results replacing the directional convexity and concavity conditions by the weaker assumptions of overrunning a super-additive function and underrunning a sub-additive function, respectively. ...

Reducible properties of graphs

P. Mihók, G. Semanišin (1995)

Discussiones Mathematicae Graph Theory

Similarity:

Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨ V ₁ ⟩_{G} \in P ₁$ and $⟨ V ₂ ⟩_{G} \in P ₂$ . The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.

On the Behavior of Power Series with Completely Additive Coefficients

Oleg Petrushov (2015)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

Consider the power series $(z) = \sum_{n = 1}^{\infty} α (n) z ⁿ$ , where α(n) is a completely additive function satisfying the condition α(p) = o(lnp) for prime numbers p. Denote by e(l/q) the root of unity $e^{2 π i l / q}$ . We give effective omega-estimates for $(e (l / p^{k}) r)$ when r → 1-. From them we deduce that if such a series has non-singular points on the unit circle, then it is a zero function.

The number of squares and $B_{h} [g]$ sets

Ben Green (2001)

Acta Arithmetica

Similarity: