Questions tagged [hypergraphs]

Use this tag for questions about *hypergraphs*, i.e. generalizations of graphs in *graph theory*, in which edges are allowed to be arbitrary subsets of vertices, instead of just pairs.

72 questions
8 views

Measure of overlap between hyperedges in a hypergraph

Given a hypergraph $H = (V,E)$, does the quantity $\max_{e\in E}\left|e\cap \bigcup_{e'\in E\setminus \{e\}}e'\right|$, i.e., the maximum number of vertices shared between one hyperedge and all the ...
22 views

How to construct conceptual models for graphs?

Construct conceptual models for the following types of graphs, using either ORM (Object-Role Modeling), ER (Entity-Relationship), or UML Class Diagrams: Directed graphs consist of nodes and directed ...
27 views

Is there a sufficiently large vertex set in a 3-uniform hypergraph, which satisfies the following condition?

Suppose $\mathcal{H}=(V,\mathcal{E})$ is a $3$-uniform hypergraph on $n$ vertices, such that for any non-empty vertex set $S\subseteq V$ with $|S|\le t$ (where $(t<n)$), there is a $v\in S$ and an ...
30 views

66 views

Edge-to-edge incidence structure of a graph

The Incidence matrix of a graph $G=(V,E)$ with $n=|V|$ numbered vertices $v_i$ and $m=|E|$ numbered edges $e_j$ is defined as the $n\times m$-matrix $M=(M_{ij})$ defined by  M_{ij}=\begin{cases}1 &...
71 views

Random Independent set in 3-uniform hypergraph

What is the maximum size of an independent set in a 3-uniform hypergraph if we choose it randomly from the set of vertices of the hypergraph? Is there any reference/idea to this problem? Thanks in ...
31 views

How to check if a separating system is minimal?

Let $\mathcal{H}$ be a minimal strongly separating system on a base set of size 20. Prove that $\mathcal{H}$ is a Sperner-system. Let $\mathcal{H}$ be a minimal strongly separating system on a base ...
268 views

Independent set in $3$-uniform hypergraph

Suppose $H$ is a $3$-uniform hypergraph such that each pair of vertices contained in at most one hyperedge. Let $\alpha(H)$ be the maximum independent set of $H.$ Independent set is a subset of ...
46 views

Expected number of multipled edges multihypergraph

I have a graph G of n vertices and with a k-list color assignment for each vertex out of $\sigma$ colors. If a choose at random all k colors for each list assignment I can model this with a k-uniform ...
12 views

Show the existence of a set $F'$, such that $F \subseteq F'$ and $|F'|=2^{n-1}$!

$F\subseteq2^{[n]}$ and it has no disjoint elements in it. Show that exists an $F'\supseteq F$, such that $F'$ still has no disjoint elements and $|F'|=2^{n-1}$! I tried to construct $F'$ of $F$ ...
89 views

what is hyper-tournament?

I know the definition of the tournament ( a directed graph obtained after assigning direction to edges of the complete graph). I tried on search on internet did not get anything. Question: What is ...
19 views

Modelling distribution of nodes' neighbours in weighted networks

I have weighted networks where weights are cosine similarities values: they are computed in function of nodes' degrees and the intersection of common neighbours. Suppose this object is a model to ...
103 views

How many hyperedges are in a (k, r) regular hypergraph?

I'm trying to write an algorithm to produce random $r$-regular $k$-uniform hypergraphs, the representation I am interested in is the incidence matrix. I've done this for the simpler case of a regular ...
38 views

69 views

acyclic decomposition of hypergraphs

The following is from the paper Arboricity: An acyclic hypergraph decomposition problem motivated by database theory by Yeow Meng Chee, Lijun Ji, Andrew Lim, Anthony K.H. Tung: Question: For an ...
49 views

Find a hypergraph such that $|e|$ even, $|e\cap f|$ odd, and $|E|>|V|$

Here is a problem I have been working on (it comes from the standard "odd-town" problem. The idea is to show that the analogy for "even-town" doesn't work). Find a hypergraph such that the edges ...
173 views

Covering a uniform hypergraph with complete $r$-partite hypergraphs

In combinatorial terms, I was wondering how many complete $r$-partite $k$-uniform hypergraphs are needed to cover the edges of the complete $n$-vertex $k$-uniform hypergraph $\binom{[n]}{k}$. An $r$-...
14 views

Is Lexicographic product of two hypergraph is same as their Wreath product??

In page 24 of the paper A survey on hypergraph product by Marc Hellmuth the lexicographic product of two hypergraph is defined as Let $H_1 = (V_1, E_1)$ and $H_2 = (V_2, E_2)$ be two hypergraphs. ...
Consider a $k$-uniform connected hypergraph with vertex set $V$ and hyperedge set $E$, as defined in https://en.wikipedia.org/wiki/Hypergraph#Symmetric_hypergraphs . We impose the following condition ...
Hypergraph $2$-colorability is NP-complete
So far all my searches for a proof of this well-known theorem have led me to the one below (Lovász 1973), reducing $k$-colorability for ordinary graphs to $2$-colorability for hypergraphs. In the ...