Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 3

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  hypertree
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Asymptotic Sharpness of Bounds on Hypertrees

100%
Lin Y., Kang L., Shan E.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
789-795
EN
The hypertree can be defined in many different ways. Katona and Szabó introduced a new, natural definition of hypertrees in uniform hypergraphs and investigated bounds on the number of edges of the hypertrees. They showed that a k-uniform hypertree on n vertices has at most [...] (nk−1) $\left( {\matrix{n \cr {k - 1} } } \right)$ edges and they conjectured that the upper bound is asymptotically sharp. Recently, Szabó verified that the conjecture holds by recursively constructing an infinite sequence of k-uniform hypertrees and making complicated analyses for it. In this note we give a short proof of the conjecture by directly constructing a sequence of k-uniform k-hypertrees.
2
Content available remote

Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees

75%
Szabó P. G. N.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
259-278
EN
In their paper, Bounds on the number of edges in hypertrees, G.Y. Katona and P.G.N. Szabó introduced a new, natural definition of hypertrees in k- uniform hypergraphs and gave lower and upper bounds on the number of edges. They also defined edge-minimal, edge-maximal and l-hypertrees and proved an upper bound on the edge number of l-hypertrees. In the present paper, we verify the asymptotic sharpness of the [...] upper bound on the number of edges of k-uniform hypertrees given in the above mentioned paper. We also make an improvement on the upper bound of the edge number of 2-hypertrees and give a general extension construction with its consequences. We give lower and upper bounds on the maximal number of edges of k-uniform edge-minimal hypertrees and a lower bound on the number of edges of k-uniform edge-maximal hypertrees. In the former case, the sharp upper bound is conjectured to be asymptotically [...] .
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Color-bounded hypergraphs, V: host graphs and subdivisions

63%
Bujtás C., Tuza Z., Voloshin V.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
223-238
EN
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 ≤ s_i ≤ t_i ≤ |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 ≤ |φ(E_i)| ≤ 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. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀. The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.