Partitions of $k$-branching trees and the reaping number of Boolean algebras

Claude Laflamme

Displaying similar documents to “Partitions of $k$ -branching trees and the reaping number of Boolean algebras”

Boolean algebras, splitting theorems, and $Δ_{2}^{0}$ sets

Michael Morley, Robert Soare (1975)

Fundamenta Mathematicae

Similarity:

$\forall_{n}$ -theories of Boolean algebras

Jan Waszkiewicz (1974)

Colloquium Mathematicae

Similarity:

Generalised irredundance in graphs: Nordhaus-Gaddum bounds

Ernest J. Cockayne, Stephen Finbow (2004)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex s of the vertex subset S of a simple graph G, we define Boolean variables p = p(s,S), q = q(s,S) and r = r(s,S) which measure existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f = f(p,q,r) may be considered as a compound existence property of S-pns. The subset S is called an f-set of G if f = 1 for all s ∈ S and the class of f-sets of G is denoted by $Ω_{f} (G)$ . Only 64 Boolean functions f can produce different classes $Ω_{f} (G)$ , special cases...

Laslett’s transform for the Boolean model in $ℝ^{d}$

Rostislav Černý (2006)

Kybernetika

Similarity:

Consider a stationary Boolean model $X$ with convex grains in $ℝ^{d}$ and let any exposed lower tangent point of $X$ be shifted towards the hyperplane $N_{0} = {x \in ℝ^{d} : x_{1} = 0}$ by the length of the part of the segment between the point and its projection onto the $N_{0}$ covered by $X$ . The resulting point process in the halfspace (the Laslett’s transform of $X$ ) is known to be stationary Poisson and of the same intensity as the original Boolean model. This result was first formulated for the planar Boolean model (see N. Cressie...

A partition of the Catalan numbers and enumeration of genealogical trees

Rainer Schimming (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers $C_{n, k}$ of all abstract genealogical trees with exactly n+1 nodes and k leaves is found by means of enumeration of code words. For each n, the $C_{n, k}$ form a partition of the n-th Catalan numer Cₙ, that means $C_{n, 1} + C_{n, 2} + . . . + C_{n, n} = C ₙ$ .

FKN Theorem on the biased cube

Piotr Nayar (2014)

Colloquium Mathematicae

Similarity:

We consider Boolean functions defined on the discrete cube $- γ, γ^{- 1} ⁿ$ equipped with a product probability measure $μ^{\otimes n}$ , where $μ = β δ_{- γ} + α δ_{γ^{- 1}}$ and γ = √(α/β). This normalization ensures that the coordinate functions ${(x_{i})}_{i = 1, . . ., n}$ are orthonormal in $L ₂ (- γ, γ^{- 1} ⁿ, μ^{\otimes n})$ . We prove that if the spectrum of a Boolean function is concentrated on the first two Fourier levels, then the function is close to a certain function of one variable. Our theorem strengthens the non-symmetric FKN Theorem due to Jendrej, Oleszkiewicz and Wojtaszczyk. Moreover,...

On BPI Restricted to Boolean Algebras of Size Continuum

Eric Hall, Kyriakos Keremedis (2013)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

(i) The statement P(ω) = “every partition of ℝ has size ≤ |ℝ|” is equivalent to the proposition R(ω) = “for every subspace Y of the Tychonoff product $2^{(ω)}$ the restriction |Y = Y ∩ B: B ∈ of the standard clopen base of $2^{(ω)}$ to Y has size ≤ |(ω)|”. (ii) In ZF, P(ω) does not imply “every partition of (ω) has a choice set”. (iii) Under P(ω) the following two statements are equivalent: (a) For every Boolean algebra of size ≤ |ℝ| every filter can be extended to an ultrafilter. (b) Every Boolean...

On $K$ -Boolean Rings

W. B. Vasantha Kandasamy (1992)

Publications du Département de mathématiques (Lyon)

Similarity:

The lattice of subvarieties of the biregularization of the variety of Boolean algebras

Jerzy Płonka (2001)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

Let τ: F → N be a type of algebras, where F is a set of fundamental operation symbols and N is the set of all positive integers. An identity φ ≈ ψ is called biregular if it has the same variables in each of it sides and it has the same fundamental operation symbols in each of it sides. For a variety V of type τ we denote by $V_{b}$ the biregularization of V, i.e. the variety of type τ defined by all biregular identities from Id(V). Let B be the variety of Boolean algebras of type $τ_{b} : +, \cdot, ´ \to N$ , where...

A note on the cubical dimension of new classes of binary trees

Kamal Kabyl, Abdelhafid Berrachedi, Éric Sopena (2015)

Czechoslovak Mathematical Journal

Similarity:

The cubical dimension of a graph $G$ is the smallest dimension of a hypercube into which $G$ is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with $2^{n}$ vertices, $n \geq 1$ , is $n$ . The 2-rooted complete binary tree of depth $n$ is obtained from two copies of the complete binary tree of depth $n$ by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice...

The rings which are Boolean

Ivan Chajda, Filip Švrček (2011)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

We study unitary rings of characteristic 2 satisfying identity $x^{p} = x$ for some natural number p. We characterize several infinite families of these rings which are Boolean, i.e., every element is idempotent. For example, it is in the case if $p = 2^{n} - 2$ or $p = 2^{n} - 5$ or $p = 2^{n} + 1$ for a suitable natural number n. Some other (more general) cases are solved for p expressed in the form $2^{q} + 2 m + 1$ or $2^{q} + 2 m$ where q is a natural number and $m \in 1, 2, . . ., 2^{q} - 1$ .

The tree property at both $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$

Laura Fontanella, Sy David Friedman (2015)

Fundamenta Mathematicae

Similarity:

We force from large cardinals a model of ZFC in which $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$ both have the tree property. We also prove that if we strengthen the large cardinal assumptions, then in the final model $ℵ_{ω + 2}$ even satisfies the super tree property.

Iterated Boolean random varieties and application to fracture statistics models

Dominique Jeulin (2016)

Applications of Mathematics

Similarity:

Models of random sets and of point processes are introduced to simulate some specific clustering of points, namely on random lines in $ℝ^{2}$ and $ℝ^{3}$ and on random planes in $ℝ^{3}$ . The corresponding point processes are special cases of Cox processes. The generating distribution function of the probability distribution of the number of points in a convex set $K$ and the Choquet capacity $T (K)$ are given. A possible application is to model point defects in materials with some degree of alignment. Theoretical...

Turán's problem and Ramsey numbers for trees

Zhi-Hong Sun, Lin-Lin Wang, Yi-Li Wu (2015)

Colloquium Mathematicae

Similarity:

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V = v ₀, v ₁, . . ., v_{n - 1}$ , $E ₁ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 4} v_{n - 2}, v_{n - 3} v_{n - 1}$ and $E ₂ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 3} v_{n - 2}, v_{n - 3} v_{n - 1}$ . For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r (T ₘ, T ₙ^{i})$ , where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

Displaying similar documents to “Partitions of k -branching trees and the reaping number of Boolean algebras”

Displaying similar documents to “Partitions of $k$ -branching trees and the reaping number of Boolean algebras”