Page 1 Next

Displaying 1 – 20 of 38

Showing per page

A backward selection procedure for approximating a discrete probability distribution by decomposable models

Francesco M. Malvestuto (2012)

Kybernetika

Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution p over a finite set V of n discrete variables and a positive integer k , find a decomposable model with tree-width k that best fits p . If is the generating hypergraph of a decomposable model and p is the estimate of p under the model, we can measure...

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

A maximum degree theorem for diameter-2-critical graphs

Teresa Haynes, Michael Henning, Lucas Merwe, Anders Yeo (2014)

Open Mathematics

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a...

A Note on a Broken-Cycle Theorem for Hypergraphs

Martin Trinks (2014)

Discussiones Mathematicae Graph Theory

Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there

A note on a conjecture on niche hypergraphs

Pawaton Kaemawichanurat, Thiradet Jiarasuksakun (2019)

Czechoslovak Mathematical Journal

For a digraph D , the niche hypergraph N ( D ) of D is the hypergraph having the same set of vertices as D and the set of hyperedges E ( N ( D ) ) = { e V ( D ) : | e | 2 and there exists a vertex v such that e = N D - ( v ) or e = N D + ( v ) } . A digraph is said to be acyclic if it has no directed cycle as a subdigraph. For a given hypergraph , the niche number n ^ ( ) is the smallest integer such that together with n ^ ( ) isolated vertices is the niche hypergraph of an acyclic digraph. C. Garske, M. Sonntag and H. M. Teichert (2016) conjectured that for a linear hypercycle...

A note on Möbius inversion over power set lattices

Klaus Dohmen (1997)

Commentationes Mathematicae Universitatis Carolinae

In this paper, we establish a theorem on Möbius inversion over power set lattices which strongly generalizes an early result of Whitney on graph colouring.

A note on packing of two copies of a hypergraph

Monika Pilśniak, Mariusz Woźniak (2007)

Discussiones Mathematicae Graph Theory

A 2-packing of a hypergraph 𝓗 is a permutation σ on V(𝓗) such that if an edge e belongs to 𝓔(𝓗), then σ (e) does not belong to 𝓔(𝓗). We prove that a hypergraph which does not contain neither empty edge ∅ nor complete edge V(𝓗) and has at most 1/2n edges is 2-packable. A 1-uniform hypergraph of order n with more than 1/2n edges shows that this result cannot be improved by increasing the size of 𝓗.

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

For an integer k 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 ) 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 [Perfect matchings in large uniform hypergraphs with large minimum collective degree, submitted]....

Currently displaying 1 – 20 of 38

Page 1 Next