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

110 questions
Filter by
Sorted by
Tagged with
10 views

### hyper graph algorithm

I want to find a reference for this problem or a same problem for my paper. I find a greedy algorithm for this problem but writing such algorithm in my paper is not common and finding a reference is ...
28 views

### Are hypergraphs more expressive than graphs?

I started studying hypergraphs theory some days ago. I know that a hypergraph is a tuple $H = (X, E)$, in which $E \subseteq \mathcal{P}(X)$ and is actually a generalisation of the notion of graph. ...
23 views

### Sperner family with small sets and large sets

I'm self-studying Bollobás' Combinatorics textbook and I am stuck on a particular question on Sperner families. We fix $k\ge 1$ and we know that the Sperner family ${\cal F}$ on the set $X = [n]$ ...
52 views

### When $L(H)=L(G)$ :: When the line graph of the hypergraph $H$ is a line graph of some multigraph $G$ ??

Introduction: The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph $\{E_1,...E_m\}$, with two hyperedges adjacent when they have a nonempty ...
32 views

### How to characterize sail-free $3$-uniform hypergraph?

Please have a look at the problem below. Given a 3-uniform hypergraph $H=(V, E),$ the matching number $\nu(H)$ is the maximum number of pairwise-disjoint edges in $E(H) .$ The cover number $\tau(H)$ ...
26 views

### Cover number and matching number in hypergraphs.

Given a 3-uniform hypergraph $H=(V, E),$ the matching number $\nu(H)$ is the maximum number of pairwise-disjoint edges in $E(H) .$ The cover number $\tau(H)$ is the size of the smallest set of ...
65 views

### Maximum number of edges on a uniform hypergraph

I need to find the maximum number of hyperedges that can be drawn in a hypergraph, such that, There are $8$ vertices. Every edge contains exactly $4$ vertices. Every edge should have exactly $2$ ...
78 views

### Find the edges in a Hypergraph

I have 8 vertices. I need to form hyperedges such that each edge should contain exactly 4 vertices and each edge should intersect with every other edge at exactly 2 vertices. How many edges are there(...
40 views

32 views

20 views

### Bound on the number of edges of a $3$-uniform hypergraph.

A $3$-uniform hypergraph $H=(V,E)$ is a hypergraph where each hyperedge is a $3$-element subset of $V$. So, let $H$ be a $3$-uniform hypergraph on $n$ vertices. Problem: I want to show that if every ...
84 views

### Specific balanced block designs

My colleague is investigating the following problem. For a given natural number $n$ construct a specific balanced block design, namely, a family $\mathcal D$ consisting of $n$-element subsets of a ...
120 views

### How do I convert a hypergraph to a graph? [closed]

I have a partitioning algorithm that works only on graphs, but my input is in the form of a hypergraph. Is there any technique that maps a hypergraph to a graph?
78 views

### Extending a theorem from bipartite graphs to tripartite hypergraphs

Here is a useful theorem on bipartite graphs. Theorem. Let $G = (X\cup Y,E)$ be a bipartite graph with $n$ vertices in each side and positive weights on the edges. If for each vertex $v \in X\cup Y$,...
71 views

### Edges only graph/hyper-graph like object?

I've been exploring a possibly novel graph/hyper-graph like structure where edges can connect other edges together and nodes are not needed. For the purposes of this question I'll refer to this sort ...
72 views

### Simple cooperative games

In the snippet below, I do not understand what is the set of players in $N$ that form ${}_{i}A.$ They say: We think of ${}_{i}A$ as the set of those voters of $N$ who vote approval level $i$ for ...