Packing of nonuniform hypergraphs - product and sum of sizes conditions

Paweł Naroski

Displaying similar documents to “Packing of nonuniform hypergraphs - product and sum of sizes conditions”

The s-packing chromatic number of a graph

Wayne Goddard, Honghai Xu (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to 1,2,...,k such that vertices with color i have pairwise distance greater than $a_{i}$ , and the S-packing chromatic number $χ_{S} (G)$ of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider...

Dimensions of non-differentiability points of Cantor functions

Yuanyuan Yao, Yunxiu Zhang, Wenxia Li (2009)

Studia Mathematica

Similarity:

For a probability vector (p₀,p₁) there exists a corresponding self-similar Borel probability measure μ supported on the Cantor set C (with the strong separation property) in ℝ generated by a contractive similitude $h_{i} (x) = a_{i} x + b_{i}$ , i = 0,1. Let S denote the set of points of C at which the probability distribution function F(x) of μ has no derivative, finite or infinite. The Hausdorff and packing dimensions of S have been found by several authors for the case that $p_{i} > a_{i}$ , i = 0,1. However, when p₀ < a₀...

Some properties of packing measure with doubling gauge

Sheng-You Wen, Zhi-Ying Wen (2004)

Studia Mathematica

Similarity:

Let g be a doubling gauge. We consider the packing measure $^{g}$ and the packing premeasure $₀^{g}$ in a metric space X. We first show that if $₀^{g} (X)$ is finite, then as a function of X, $₀^{g}$ has a kind of “outer regularity”. Then we prove that if X is complete separable, then $λ s u p ₀^{g} (F) \leq^{g} (B) \leq s u p ₀^{g} (F)$ for every Borel subset B of X, where the supremum is taken over all compact subsets of B having finite $₀^{g}$ -premeasure, and λ is a positive number depending only on the doubling gauge g. As an application, we show that for every doubling...

Packing constant for Cesàro-Orlicz sequence spaces

Zhen-Hua Ma, Li-Ning Jiang, Qiao-Ling Xin (2016)

Czechoslovak Mathematical Journal

Similarity:

The packing constant is an important and interesting geometric parameter of Banach spaces. Inspired by the packing constant for Orlicz sequence spaces, the main purpose of this paper is calculating the Kottman constant and the packing constant of the Cesàro-Orlicz sequence spaces ( ${ces}_{φ}$ ) defined by an Orlicz function $φ$ equipped with the Luxemburg norm. In order to compute the constants, the paper gives two formulas. On the base of these formulas one can easily obtain the packing constant...

Packing four copies of a tree into a complete bipartite graph

Liqun Pu, Yuan Tang, Xiaoli Gao (2022)

Czechoslovak Mathematical Journal

Similarity:

In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree $T$ of order $n$ and each integer $k \geq 2$ , there is a $k$ -packing of $T$ in a complete bipartite graph $B_{n + k - 1}$ whose order is $n + k - 1$ . We prove the conjecture is true for $k = 4$ .

Constructing universally small subsets of a given packing index in Polish groups

Taras Banakh, Nadya Lyaskovska (2011)

Colloquium Mathematicae

Similarity:

A subset of a Polish space X is called universally small if it belongs to each ccc σ-ideal with Borel base on X. Under CH in each uncountable Abelian Polish group G we construct a universally small subset A₀ ⊂ G such that |A₀ ∩ gA₀| = for each g ∈ G. For each cardinal number κ ∈ [5,⁺] the set A₀ contains a universally small subset A of G with sharp packing index $p a c k ♯ (A_{κ}) = s u p | | ⁺ : \subset {g A}_{g \in G} i s d i s j o i n t$ equal to κ.

Perturbing the hexagonal circle packing: a percolation perspective

Itai Benjamini, Alexandre Stauffer (2013)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider the hexagonal circle packing with radius $1 / 2$ and perturb it by letting the circles move as independent Brownian motions for time $t$ . It is shown that, for large enough $t$ , if $𝛱_{t}$ is the point process given by the center of the circles at time $t$ , then, as $t \to \infty$ , the critical radius for circles centered at $𝛱_{t}$ to contain an infinite component converges to that of continuum percolation (which was shown – based on a Monte Carlo estimate – by Balister, Bollobás and Walters to be strictly...

Sum labellings of cycle hypergraphs

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph $_{d ̲, [d ̅]} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ \leq | e | \leq [d ̅] \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y ₁, . . ., y_{σ} \notin V$ such that $\cup y ₁, . . ., y_{σ}$ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings...

Continuous rearrangements of the Haar system in $H_{p}$ for 0 < p < ∞

Krzysztof Smela (2008)

Studia Mathematica

Similarity:

We prove three theorems on linear operators $T_{τ, p} : H_{p} (ℬ) \to H_{p}$ induced by rearrangement of a subsequence of a Haar system. We find a sufficient and necessary condition for $T_{τ, p}$ to be continuous for 0 < p < ∞.

Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás, Zsolt Tuza, Vitaly Voloshin (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = E₁,...,Eₘ, together with integers $s_{i}$ and $t_{i}$ satisfying $1 \leq s_{i} \leq t_{i} \leq | E_{i} |$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_{i}$ satisfies $s_{i} \leq | φ (E_{i}) | \leq t_{i}$ . The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a “host graph”, that means a graph G on the same vertex set X as ℋ, such that each $E_{i}$ induces a connected subgraph in G....

The sum number of d-partite complete hypergraphs

Hanns-Martin Teichert (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph $⁺_{d} (S) = (V,)$ , where V = S and $= v ₁, . . ., v_{d} : (i \neq j \Rightarrow v_{i} \neq v_{j}) \land \sum_{i = 1}^{d} v_{i} \in S$ . For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $w ₁, . . ., w_{σ} \notin V$ such that $\cup w ₁, . . ., w_{σ}$ is a sum hypergraph. In this paper, we prove $σ (_{n ₁, . . ., n_{d}}^{d}) = 1 + \sum_{i = 1}^{d} (n_{i} - 1) + m i n 0, ⌈ 1 / 2 (\sum_{i = 1}^{d - 1} (n_{i} - 1) - n_{d}) ⌉$ , where $_{n ₁, . . ., n_{d}}^{d}$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

Classes of hypergraphs with sum number one

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph $ℋ_{d ̲, d ̅} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ < | e | < d ̅ \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices $w ₁, . . ., w_{σ} \notin V$ such that $ℋ \cup w ₁, . . ., w_{σ}$ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition...

Some results on packing in Orlicz sequence spaces

Y. Q. Yan (2001)

Studia Mathematica

Similarity:

We present monotonicity theorems for index functions of N-fuctions, and obtain formulas for exact values of packing constants. In particular, we show that the Orlicz sequence space $l^{(N)}$ generated by the N-function N(v) = (1+|v|)ln(1+|v|) - |v| with Luxemburg norm has the Kottman constant $K (l^{(N)}) = N^{- 1} (1) / N^{- 1} (1 / 2)$ , which answers M. M. Rao and Z. D. Ren’s [8] problem.

On the asymptotics of counting functions for Ahlfors regular sets

Dušan Pokorný, Marc Rauch (2022)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We deal with the so-called Ahlfors regular sets (also known as $s$ -regular sets) in metric spaces. First we show that those sets correspond to a certain class of tree-like structures. Building on this observation we then study the following question: Under which conditions does the limit ${lim}_{ε \to 0 +} ε^{s} N (ε, K)$ exist, where $K$ is an $s$ -regular set and $N (ε, K)$ is for instance the $ε$ -packing number of $K$ ?

Two variants of the size Ramsey number

Andrzej Kurek, Andrzej Ruciński (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m (G) = m a x_{F \subseteq G} | E (F) | / | V (F) |$ and define the Ramsey density $m_{i n f} (H, r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{i n f} (H, r) = (R - 1) / 2$ , where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited...

Characterization of local dimension functions of subsets of $ℝ^{d}$

L. Olsen (2005)

Colloquium Mathematicae

Similarity:

For a subset $E \subseteq ℝ^{d}$ and $x \in ℝ^{d}$ , the local Hausdorff dimension function of E at x is defined by $d i m_{H, l o c} (x, E) = l i m_{r ↘ 0} d i m_{H} (E \cap B (x, r))$ where $d i m_{H}$ denotes the Hausdorff dimension. We give a complete characterization of the set of functions that are local Hausdorff dimension functions. In fact, we prove a significantly more general result, namely, we give a complete characterization of those functions that are local dimension functions of an arbitrary regular dimension index.

Mean value densities for temperatures

N. Suzuki, N. A. Watson (2003)

Colloquium Mathematicae

Similarity:

A positive measurable function K on a domain D in $ℝ^{n + 1}$ is called a mean value density for temperatures if $u (0, 0) = \int \int_{D} K (x, t) u (x, t) d x d t$ for all temperatures u on D̅. We construct such a density for some domains. The existence of a bounded density and a density which is bounded away from zero on D is also discussed.

A density estimate for the $3 x + 1$ problem

Ivan Korec (1994)

Mathematica Slovaca

Similarity:

Localization of jumps of the point-distinguishing chromatic index of $K_{n, n}$

Mirko Horňák, Roman Soták (1997)

Discussiones Mathematicae Graph Theory

Similarity:

The point-distinguishing chromatic index of a graph represents the minimum number of colours in its edge colouring such that each vertex is distinguished by the set of colours of edges incident with it. Asymptotic information on jumps of the point-distinguishing chromatic index of $K_{n, n}$ is found.

Fires on trees

Jean Bertoin (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider random dynamics on the edges of a uniform Cayley tree with $n$ vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate $n^{- α}$ on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as $n \to \infty$ , the terminal density of fireproof...

Indestructible colourings and rainbow Ramsey theorems

Lajos Soukup (2009)

Fundamenta Mathematicae

Similarity:

We show that if a colouring c establishes ω₂ ↛ [(ω₁:ω)]² then c establishes this negative partition relation in each Cohen-generic extension of the ground model, i.e. this property of c is Cohen-indestructible. This result yields a negative answer to a question of Erdős and Hajnal: it is consistent that GCH holds and there is a colouring c:[ω₂]² → 2 establishing ω₂ ↛ [(ω₁:ω)]₂ such that some colouring g:[ω₁]² → 2 does not embed into c. It is also consistent that $2^{ω ₁}$ is arbitrarily large,...

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

Similarity:

We consider, for a positive integer $k$ , induced subgraphs in which each component has order at most $k$ . Such a subgraph is said to be $k$ -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$ -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for...

Construction of an Uncountable Difference between Φ(B) and $Φ_{f} (B)$

Josh Campbell, David Swanson (2008)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

We construct a set B and homeomorphism f where f and $f^{- 1}$ have property N such that the symmetric difference between the sets of density points and of f-density points of B is uncountable.