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.
9 questions
16
votes
2
answers
4k
views
Minimum Cake Cutting for a Party
You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be prepared, ...
- 50.5k
5
votes
1
answer
564
views
Bruhat-Tits Building of $PGL_3$: What does it look like?
I am very new to this topic, and my background is mostly in graph theory and basic algebra. What I want for now is to understand the structure of the dimension $2$ complex $\mathcal{B}(PGL_3(K))$ ...
- 2,637
5
votes
1
answer
1k
views
three-uniform hypergraph on $n$ vertices with at least $n/3$ edges contains an independent set of size at least $\frac{2n^{3/2}}{3\sqrt{3m}}$
Here is question 3 from chapter 3 Part 1 of The Probabilistic Method, 4th edition.
Prove that every three-uniform hypergraph with $n$ vertices and $m \ge n∕3$ edges contains an independent set (i.e., ...
- 999
5
votes
1
answer
308
views
Threshold probability of the 3-uniform hypertriangle
I am stuck on a random hypergraph problem (I am encountering random hypergraphs for the very first time).
Let $G_{3}(n, p)$ be a binomial 3-uniform hypergraph. Find a threshold probability for ...
- 523
3
votes
2
answers
1k
views
What is a cycle hypergraph?
What is a cycle hypergraph? Could someone give me good reference or illustrate with a few examples?
- 6,341
2
votes
2
answers
273
views
Is $\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}(k-1)^{k-1}+(r-2)^r=0$ right?
How to prove $$\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}(k-1)^{k-1}+(r-2)^r=0$$
I met this function when I tried to give another proof of the known lower bound of Tur\'an functions of complete ...
- 814
1
vote
1
answer
161
views
Intersecting r-families with any two intersects in more than s elements.
There is a well-known fact that if $F$ is a family of $r$-subsets of an $n$-set no two of which intersect in exactly $s$ elements then $\vert F \vert \leq n^{\max\{s, r-s-1\}}$.
But are there any ...
0
votes
2
answers
439
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(...
- 67
0
votes
0
answers
398
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$ ...
- 67