Questions tagged [hypergraphs]
The hypergraphs tag has no usage guidance.
4
questions
19
votes
4
answers
1k
views
"All-different hypergraph coloring" - known problem?
I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
- 1,023
21
votes
2
answers
3k
views
Recognizing line graphs of hypergraphs
The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection.
A hypergraph is an $r$-...
- 2,477
10
votes
4
answers
771
views
What are the root difficulties in going from graphs to hypergraphs?
There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems ...
- 6,970
3
votes
2
answers
132
views
Lower bound on the largest restrained cubic subset
Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:
Each row in the cube (in any of the three directions) has exactly 2 ...
- 225