Asymptotic Sharpness of Bounds on Hypertrees

Yi Lin; Liying Kang; Erfang Shan

Displaying similar documents to “Asymptotic Sharpness of Bounds on Hypertrees”

A note on k-uniform self-complementary hypergraphs of given order

Artur Szymański, A. Paweł Wojda (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We prove that a k-uniform self-complementary hypergraph of order n exists, if and only if $(\binom{n}{k})$ is even.

Self-complementary hypergraphs

A. Paweł Wojda (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A k-uniform hypergraph H = (V;E) is called self-complementary if there is a permutation σ:V → V, called self-complementing, such that for every k-subset e of V, e ∈ E if and only if σ(e) ∉ E. In other words, H is isomorphic with $H^{'} = (V; (\binom{V}{k}) - E)$ . In the present paper, for every k, (1 ≤ k ≤ n), we give a characterization of self-complementig permutations of k-uniform self-complementary hypergraphs of the order n. This characterization implies the well known results for self-complementing permutations...

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...

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....

A note on perfect matchings in uniform hypergraphs with large minimum collective degree

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, Endre Szemerédi (2008)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

For an integer $k \geq 2$ and a $k$ -uniform hypergraph $H$ , let $δ_{k - 1} (H)$ be the largest integer $d$ such that every $(k - 1)$ -element set of vertices of $H$ belongs to at least $d$ edges of $H$ . Further, let $t (k, n)$ be the smallest integer $t$ such that every $k$ -uniform hypergraph on $n$ vertices and with $δ_{k - 1} (H) \geq t$ contains a perfect matching. The parameter $t (k, n)$ has been completely determined for all $k$ and large $n$ divisible by $k$ by Rödl, Ruci’nski, and Szemerédi in [, submitted]. The values of $t (k, n)$ are very close to $n / 2 - k$ . In fact, the function $t (k, n) = n / 2 - k + c_{n, k}$ ,...

Radio k-colorings of paths

Gary Chartrand, Ladislav Nebeský, Ping Zhang (2004)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings...

Diagonalization in proof complexity

Jan Krajíček (2004)

Fundamenta Mathematicae

Similarity:

We study diagonalization in the context of implicit proofs of [10]. We prove that at least one of the following three conjectures is true: ∙ There is a function f: 0,1* → 0,1 computable in that has circuit complexity $2^{Ω (n)}$ . ∙ ≠ co . ∙ There is no p-optimal propositional proof system. We note that a variant of the statement (either ≠ co or ∩ co contains a function $2^{Ω (n)}$ hard on average) seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that...

The generalized Day norm. Part I. Properties

Monika Budzyńska, Aleksandra Grzesik, Mariola Kot (2017)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we introduce a modification of the Day norm in $c_{0} (Γ)$ and investigate properties of this norm.

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.

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...

Low-discrepancy point sets for non-uniform measures

Christoph Aistleitner, Josef Dick (2014)

Acta Arithmetica

Similarity:

We prove several results concerning the existence of low-discrepancy point sets with respect to an arbitrary non-uniform measure μ on the d-dimensional unit cube. We improve a theorem of Beck, by showing that for any d ≥ 1, N ≥ 1, and any non-negative, normalized Borel measure μ on ${[0, 1]}^{d}$ there exists a point set $x_{1}, . . ., x_{N} \in {[0, 1]}^{d}$ whose star-discrepancy with respect to μ is of order $D_{N} * (x_{1}, . . ., x_{N}; μ) ≪ ({(l o g N)}^{(3 d + 1) / 2}) / N$ . For the proof we use a theorem of Banaszczyk concerning the balancing of vectors, which implies an upper bound for the linear...

Improved upper bounds for nearly antipodal chromatic number of paths

Yu-Fa Shen, Guo-Ping Zheng, Wen-Jie HeK (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $a c^{'} (P ₙ) \leq (\binom{n - 2}{2}) + 2$ for every positive integer n, where ac’(Pₙ) denotes the nearly antipodal chromatic number of Pₙ. In this paper we show that $a c^{'} (P ₙ) \leq (\binom{n - 2}{2}) - n / 2 - ⎣ 10 / n ⎦ + 7$ if n is even positive integer and n ≥ 10, and $a c^{'} (P ₙ) \leq (\binom{n - 2}{2}) - (n - 1) / 2 - ⎣ 13 / n ⎦ + 8$ if n is odd positive integer and n ≥ 13. For all even positive integers n ≥ 10 and all odd positive integers n ≥ 13, these results improve the upper bounds for nearly antipodal chromatic number of Pₙ.

Lower bounds on signed edge total domination numbers in graphs

H. Karami, S. M. Sheikholeslami, Abdollah Khodkar (2008)

Czechoslovak Mathematical Journal

Similarity:

The open neighborhood $N_{G} (e)$ of an edge $e$ in a graph $G$ is the set consisting of all edges having a common end-vertex with $e$ . Let $f$ be a function on $E (G)$ , the edge set of $G$ , into the set ${- 1, 1}$ . If $\sum_{x \in N_{G} (e)} f (x) \geq 1$ for each $e \in E (G)$ , then $f$ is called a signed edge total dominating function of $G$ . The minimum of the values $\sum_{e \in E (G)} f (e)$ , taken over all signed edge total dominating function $f$ of $G$ , is called the signed edge total domination number of $G$ and is denoted by $γ_{s t}^{'} (G)$ . Obviously, $γ_{s t}^{'} (G)$ is defined only for graphs $G$ which have no connected...

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.