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.
174 questions
2
votes
0
answers
52
views
Size of family of pairs of edges overlapping at exactly 1 vertex in a non two colorable hypergraph
Show that every n-uniform non 2 colorable hypergraph $H$ contains atleast $\frac{n}{2} {2n-1 \choose n-1}$ unordered pairs of edges each overalapping at exactly 1 vertex. I came across this problem in ...
3
votes
0
answers
50
views
Planted Matching in Hypergraphs
I’m working on the planted perfect matching problem in random $k$-uniform hypergraphs $k \ge 3$, and I’m stuck on rigorizing the impossibility (lower bound) side of what looks like the information-...
- 31
1
vote
0
answers
61
views
Counter-example for Brooks Theorem for Hypergraphs
In Hypergraphs (C. Berge), Theorem 2 in Chapter 4 (Colorings) is as follows, which is a Brooks-type result for hypergraphs:
Let $H$ be a linear hypergraph without loops. Then $\chi(H) \leq \Delta(H)$,...
- 164
0
votes
0
answers
23
views
Find the Minimum Spanning Hyperedge
I am looking for an algorithm that finds a Tree that spans a set of Terminals in a hypergraph. Let's say we have (3) terminals {A, B, C}. I define the Tree as a set of hyperedges and edges:
$ T \equiv ...
4
votes
2
answers
188
views
Does this property completely define SET-like games?
In the game SET each card has $4$ properties (color, filling, shape and number), each with $3$ possible values, for a total of $3 ^ 4 = 81$ cards. We can think of cards as elements of $\{0,1,2\} ^ 4$. ...
- 659
3
votes
1
answer
88
views
Partitioning a uniform and regular hypergraph
The problem
I've been thinking about this problem for a few months but have made virtually no progress asides from discarting possible proof ideas. Suppose you have a $3$-uniform hypergraph $H$ that ...
- 5,452
0
votes
0
answers
129
views
Can the MRB constant be interpreted via alternating sums of edge lengths of hypercubes with diameter $n$
The MRB constant is the limit point defined by
$ \underset{x\to \infty }{\text{lim}}\left(\sum _{n=1}^{2 x} (-1)^n n^{1/n}\right)$
This sequence involves the nth roots of $n$, which can be interpreted ...
- 309
0
votes
0
answers
54
views
Is there a term for this class of hypergraphs?
Given an undirected graph $G = (V,E)$, and a set of nodes $W$ that is disjoint from $V$, we can construct a hypergraph $H$ in the following way:
The nodes of $H$ are $V\cup W$;
Each hyperedge of $H$ ...
- 11.6k
2
votes
0
answers
94
views
Coloring hypercube(related: impossible chessboard in 3blue1brown)
Question
For the power of two dim (i.e.,, $n=2^m$) hypercube,
can we color hypercube satisfying the following condition? and if it is possible, how many solutions there are if m varies?
condition:
...
- 23
2
votes
1
answer
196
views
Oddtown problem with specific intersection size?
The algebraic proof of the following problem is very nice: assume $H$ is a 3-uniform hypergraph on $n$ vertices. What is the maximum number of edges of $H$ such that there does not exist two edges ...
- 2,504
4
votes
3
answers
317
views
maximum number of $4$-edges with no two sharing exactly two vertices
Let $H$ be the 4-uniform hypergraph with two edges $e,f$ such that $|e\cap f|=2$.
I am wondering what is the maximum number $T$ of edges in a 4-uniform hypergraph on $n$ vertices that does not contain ...
- 2,504
0
votes
1
answer
72
views
Maximizing the number of generated triplets that are in a set
I don't have much math experience and feel out of my depth with this problem, so apologies in advance.
Given the sets $C$, $V$, and $S$ where $S \subseteq C \times V \times C$:
Find sets $c \subseteq ...
- 103
0
votes
0
answers
61
views
Tesselating nets of hypercubes
A net of hypercubes is a unique unfolding of a higher-dimension hypercube. A n-cube can unfold into many distinct nets consisting of $2n$ (n-1)-cubes. There are 11 unique unfoldings of a cube into 2D ...
- 327
2
votes
0
answers
241
views
Max number of edges in $p$-uniform hypergraph on $n$ vertices with $|E_1\cap E_2|\le 1$ for any two distinct edges $E_1, E_2$
This is an equivalent formulation (with different notations!) of the problem from a recent AoPS thread (which is unsolved for one and half month):
Given a $p$-uniform hypergraph $H=(V, \mathcal E)$ ...
- 87
1
vote
0
answers
53
views
Complexity of counting perfect matchings in 3-uniform Hypergraphs (X3C)
I am aware that counting perfect matchings in graphs is #P-complete. I want to know what the complexity is in 3-uniform hypergraphs, i.e., X3C (and more generally in hypergraphs). You could also ...
