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.
173 questions
3
votes
0
answers
44
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
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 ...
3
votes
1
answer
82
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,288
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
1
answer
167
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,498
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
2
votes
0
answers
229
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
3
votes
0
answers
79
views
3-uniform hypergraphs with only disjoint perfect matchings
I am searching for 3-uniform hypergraphs with only disjoint perfect matchings (i.e., every hyperedge only appears in at most one of the perfect matchings).
For example, $K_6^3$ has 10 disjoint perfect ...
9
votes
1
answer
529
views
Coarse-graining a bounded-incidence hypergraph
Let $G$ be a connected hypergraph with vertex-set $V$ and hyperedge-set $E \subseteq 2^V\smallsetminus \{\emptyset\}$. Assume that every vertex is part of at most $\Delta$ hyperedges and every ...
- 6,114
1
vote
1
answer
212
views
Connected partitions of bounded-degree bounded-rank hypergraphs
Some definitions: A hypergraph has vertices and hyperedges, where each hyperedge is a nonempty subset of the vertex-set (I am allowing singletons) and no two hyperedges are equal. The degree of a ...
- 6,114
0
votes
0
answers
48
views
Extending a k-uniform hypergraph
Let $H = (V, E)$ be a $k$-uniform hypergraph of order $n = \vert V \vert$ and size $ t = \vert E \vert$ < Bin(n,k). Assume that for any vertex cover $C$ in $H$, we have $\vert C \vert \ll n$.
I ...
- 1
3
votes
0
answers
401
views
Definition of hypergraph homomorphism
W.Dörfler and D.A.Waller's paper "A category-theoretical approach to hypergraphs" gives the following definitions:
A hypergraph is a triple $H = (V,E,f)$ where $V$ is the set of vertices, $...
- 18.5k
0
votes
1
answer
108
views
Hypergraphs as a category
If we regard hypergraphs $H=(V,E)$ as the objects, where $V$ is a set and $E\subseteq {\cal P}(V)$, what is the "right", or commonly used notion of morphism for that category?
- 2,858
0
votes
1
answer
76
views
what does "relation" mean in the Category of hypergraphs?
in the ncatlab https://ncatlab.org/nlab/show/hypergraph they defined the category of hypergraphs:
SimpHGrph has objects consisting of a pair of sets (V,H) equipped with a relation R⊆V×H, and morphisms ...
2
votes
1
answer
161
views
Is any underlying Hypergraph of a finite cubical complex contained in the Hypergraph of cubical complex formed by n-cube,with n sufficient large?
This question arises from simple observation that an oritentated finite simplicial complex must be contained in a sufficient large simplicial complex formed by n-simplex(Take n as number of vertexes ...
- 491
2
votes
2
answers
445
views
Ruzsa–Szemerédi problem for regular graphs
The Ruzsa–Szemerédi problem asks for the maximum number of edges in a locally linear graph, i. e. a graph in which every edge belongs to a unique triangle (equivalently, any two adjacent vertices have ...
- 1,861
1
vote
1
answer
74
views
Prove that $A_i$ has at least $1$ member that is not colored.
Let $A_1, A_2, \dots , A_n$ be subsets of $\{1, 2,\dots , n\}$ of size $3$. Prove that $\lfloor \frac{n}{3}\rfloor$ members of $\{1, 2,\dots , n\}$ can be colored such that each $A_i$ has at least $1$ ...
- 1,811
1
vote
1
answer
213
views
Sufficient condition for a hypergraph to be 2-colorable
Let $H=(V,E)$ be a hypergraph with the property that each edge has at least $k \ge 2$ vertices. Show that if for each edge $e$ of $H(E)$ holds
$$ 8 \sum_{j \ge k} \frac{d_{e,j}}{2^j} \le 1$$
where $...
- 4,414
1
vote
1
answer
42
views
Tura\'an density of an $r$-uniform hypergraph $H$.
The Tur'an density of an $r$-uniform hypergraph $H$ is $$\lim\limits_{n\rightarrow\infty}\frac{ex(n,H)}{n\choose r}$$.
It is known that this is well defined. To prove this, it is enough to show that ...
- 317
1
vote
1
answer
51
views
Multiset Covers with a Uniformity Condition
I was playing around with the indices of tuples of functions, and these objects came up naturally. Is there a name for them? Are there any resources on them that provide some properties or even a ...
- 626
2
votes
0
answers
144
views
Discrepancy of random bipartite graphs
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a random bipartite graph on $X \sqcup Y$ in an Erdos-Renyi fashion ...
- 579
1
vote
0
answers
96
views
Check if adjacency tensor of hypergraph is irreducible
Consider an m-uniform, n-dimensional hypergraph. It's adjacency tensor is an
$\overbrace{(n \times n \times ... \times n)}^{m}$
-dimensional tensor $T$. As shown in [1], to calculate the $(H)$-...
- 309
0
votes
0
answers
35
views
How to find the maximum number of edges that exactly contain x vertices in a k-uniform hypergraph？
Help me please. I really need some articles about this problem. Or are there any other extremal k-uniform hypergraph about this problem?
5
votes
1
answer
136
views
Hypergraph variant of handshake problem.
I came across this well known problem that goes something like this.
If $n$ people shake hands with each other. How many handshakes will be there in total?
The question can be interpreted as asking ...
- 51
1
vote
1
answer
84
views
Example of non-(normal) and non-($\tau$-normal) hypergraphs?
According to Normal Hypergraphs and the Weak Perfect Graph Conjecture (these are definitions!):
A hypergraph $H$ is normal if $\rho(H') \geq \delta(H')$ for every $H'$ partial hypergraph of $H$
A ...
- 1,058