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
0
votes
0answers
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 ...
3
votes
1answer
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.
...
2
votes
1answer
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]$ ...
1
vote
0answers
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 ...
2
votes
0answers
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)$ ...
0
votes
1answer
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 ...
0
votes
0answers
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$ ...
0
votes
2answers
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(...
3
votes
0answers
40 views
A sequence of partitions that splits up every triple [duplicate]
The question
We are given a set of size $m$, which we can assume to be the set $[m] = \{1,2,\dots,m\}$.
Say that a sequence $(A_i,B_i,C_i)_{i=1}^k$ triple-splits the set $[m]$ if:
For each $i$, $(A_i,...
4
votes
2answers
54 views
Topologies and sigma-algebras as “hypergraphs” containing an “edge” having 0 endpoints
A hypergraph $H$ is a pair $H=(X,E)$ where $X$ is a set of elements called nodes and $E$ is a set of non-empty subsets of $X$ called hyperedges.
I'm wondering about the motivation behind specifying ...
0
votes
1answer
24 views
The width of a hypergraph
In this paper, the width of a hypergraph $H$ is defined as the minimum integer $t$ for which there exists a subset $T$ of $t$ hyperedges in $H$, such that every hyperedge of $H$ intersects at least ...
1
vote
0answers
32 views
Is underlying hypergraph isomorphism of simplicial 'stuff'' equivalent to topological equivalence?
Assume that a piece-wise linear entity can be (heterogeneously) triangulated into a simplicial structure. Does not the underlying hypergraph (without the positional information of simplices) ...
0
votes
0answers
26 views
What characterizes the adjacency matrix of a tripartite hypergraph?
The adjacency matrix of a graph $G = (V,E)$ is a matrix with $|V|$ rows and $|E|$ columns, in which element $v,e$ is $1$ if node $v$ is adjacent to edge $e$, and $0$ otherwise.
In bipartite graphs, ...
0
votes
1answer
31 views
Recover premetric from subset of topology
From Is a symmetric premetric space a topological space? I am aware that a premetric $d: X \times X \rightarrow \mathbb R$ defined for elements of a set $X$ induces a topology $\tau$ on the set, so ...
1
vote
1answer
39 views
Prove that all $k$-uniform hypergraphs $H$ with $e(H) \leq \frac{4^{k-1}}{3^{k}}$ admit a rainbow 4-colouring
I’m trying to apply the probabilistic method on this problem, and I’d like some checking on my solution.
We say a $4$-colouring of the vertices of a $k$-uniform hypergraph is rainbow if every edge ...
4
votes
1answer
42 views
Notion of distance in a Hypergraph
I've been trying to find canonical notions of distance in hypergraphs which generalize the notion of distance in graphs. I was hoping for a distance which also encodes a metric on two subsets of the ...
0
votes
0answers
9 views
In a hypergraph, the edges are selected to be in some set with probability $p$. What is the probability that some vertex $v$ is not in that set?
For a $r$-uniform hypergraph $H$ on $n$ vertices with edge set $E$, each edge is picked independently to be in $E' \subset E$ with probability $p$. For a vertex $v \in H$ with deg$(v) = k$, I want to ...
0
votes
0answers
13 views
Does this definition for cycles in hypergraphs appear anywhere?
I'm looking for a definition of a cycle on a $k$-uniform hypergraph that is equivalent to the following definition:
Let $H=(V,E)$ be a $k$-uniform (each hyperedge contains $k$ vertices) hypergraph on $...
0
votes
0answers
32 views
Probability of a vertex not belonging to a set of edges in a random hypergraph.
Let $H(n,p)$ be a $r$-uniform random hypergraph on $n$ vertices, with vertex set $V$ and edge set $E$. Let $E' \subset E$ be a set of edges with some known characteristics, and $V' = V \setminus \{u_i:...
0
votes
1answer
55 views
Application of a lemma to prove Pippenger's 1989 Theorem.
This is a quite involved question so I'd be happy just to be shown how to understand some small parts. I'm trying to read these slides, in which the lemma in slide 25 is used to prove Pippenger's ...
2
votes
1answer
60 views
Why is the finite-projective-plane minus a single edge r-partite?
Let $P_r$ be the finite projective plane in which each line contains $r$ points (when it exists). For example, $P_2$ is a triangle, $P_3$ is the Fano plane, and $P_r$ exists whenever $r-1$ is the ...
1
vote
1answer
20 views
Value $p$ that makes the random hypergraph $H^{(k)}(n,p)$ a good cover?
I need help understanding the following argument.
Definition. A $(k, t)$-covering of $[n]$ is a family of $k$-sets $\mathcal{F} \subseteq\left(\begin{array}{c}{[n]} \\ k\end{array}\right)$ such that ...
1
vote
1answer
49 views
Which generalization of bipartite graphs is stronger?
Here are some ways to generalize the notion of a bipartite graph to hypergraphs:
A hypergraph is called 2-colorable if its vertices can be 2-colored such that each hyperedge of size at least 2 ...
1
vote
1answer
51 views
Which planar subgraph of hypercube Q4 has the maximum number of edges?
I believe Q3 is the biggest planar subgraph of Q4, but I think that by drawing four edges at the outermost vertices of Q3 I can obtain a bigger subgraph. Am I thinking correctly?
0
votes
1answer
232 views
How to find the crossing number of a hypercube Q4?
I'm struggling to find the crossing number of Q4, I think I have trouble visualizing the cube and finding the crossing number. Any idea what theorem or lemma I can use?
2
votes
1answer
40 views
Can all Hypergraphs be Embedded in 3D Space?
I once read that every graph there is could be embedded in 3D Space without edges crossing one another and that only planar graphs can be embedded in 2D such that their edges do not cross. I was ...
0
votes
1answer
39 views
Breaking a hypergraph into two hypergraphs of smaller degree
The degree of a vertex in a hypergraph is defined as the number of hyperedges in which it occurs. The degree of the hypergraph is the maximum of the degrees of the vertices.
Given a hypergraph $\...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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?
6
votes
0answers
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$,...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
24 views
Relation between minimum degrees of hypergraphs
It is indicated by Page 146 of https://link.springer.com/content/pdf/10.1007%2F978-3-319-24298-9.pdf : an $n$-vertex $k$-uniform hypergraph $H$ has vertex-set $V=[n]$ and edge-set $E\subseteq\binom{[n]...
1
vote
0answers
40 views
Rank of incidence matrix of Hamming graph
Consider a Hamming graph $H(d, q)$.
What is the rank of its incidence matrix?
Hypergraph
A Hamming graph can be seen in two ways:
Take the numbers $0$ until $q^d - 1$ and represent them in base $q$....
0
votes
0answers
16 views
Calculating network density in a hypergraph
Is it possible to calculate network density with a hypergraph? Network density is defined as the proportion of edges to the number of possible edges. Does this generalize to hypergraphs? If so, does ...
1
vote
1answer
69 views
In a $k$-graph H, calculate the probability that the last vertex of some edge e is the first vertex of some other edge f.
Let $H$ be a $k$-uniform hypergraph with $m$ edges. For each vertex $v \in V(H)$, we independently sample $x_v \sim U([0,1])$, a uniformly random number in $[0,1]$. We then order the vertices in ...
1
vote
1answer
55 views
For $t \geq 3$, if $n \geq R^{(3)}(t,t)$, then n points in $\mathbb{R}^2$ always contain either t collinear points, or t points in convex position.
Here $R^{(3)}(t,t)$ is the 3-uniform Ramsey number in the two colors red and blue.
I'd like to ask for some hints. I've tried giving the 3-sets of $n$ points a meaningful coloring (e.g. red if the 3 ...
0
votes
0answers
36 views
Let $H$ be a $k$-uniform hypergraph, for some $k \geq 2$, such that $|e \cap f| \neq 1$ for any two edges $e,f$. Show that $H$ is two-colourable.
This is an exercise I'm doing. Please have a look at my attempted solution below.
In our class we define a proper coloring of a graph $H$ is one where none of the edges is monochromatic.
Assume for ...
0
votes
0answers
16 views
How to count all nodes within a given radius R in a polytope graph topology?
In graphs with topologies nD-Mesh and nD-HyperCube (n dimensional), I am trying to find a model to calculate the number of nodes ...
2
votes
1answer
113 views
Bound for the number of edges of a linear uniform hypergraph
A hypergraph $H$ is a pair $H = (X,E)$ where $X$ is a set of elements called nodes or vertices, and $E$ is a set of non-empty subsets of $X$ called hyperedges or edges.
We say a hypergraph is $k$-...
0
votes
1answer
38 views
Small question about vertices in hypergraphs
Say we have a hypergraph $H$ and a (hyper)edge $E$. Does that mean that all vertices in $E$ are connected?
So if $E= \{a,b,c\}$ does that necessarily mean $a$ and $b$ are connected?
And does that ...
1
vote
1answer
65 views
Minimum Traversal of Complete Graph?
I've encountered a question in my Graph Theory course that I don't quite understand. The instructor never went through what exactly the "function" used in this question is, so I'm looking for some ...
1
vote
0answers
54 views
How to construct conceptual models for graphs?
Construct conceptual models for the following types of graphs, using either ORM
(Object-Role Modeling), ER (Entity-Relationship), or UML Class Diagrams:
Directed graphs consist of nodes and directed ...
1
vote
0answers
31 views
Is there a sufficiently large vertex set in a 3-uniform hypergraph, which satisfies the following condition?
Suppose $\mathcal{H}=(V,\mathcal{E})$ is a $3$-uniform hypergraph on $n$ vertices, such that for any non-empty vertex set $S\subseteq V$ with $|S|\le t$ (where $(t<n)$), there is a $v\in S$ and an ...
4
votes
1answer
34 views
Number of unlabeled hypergraphs (A003180)
I'm looking for the number of unlabeled hypergraphs on n nodes and stumbled upon the comments of A003180 in OEIS. Can somebody please explain to me how that sequence relates to the number of unlabeled ...
1
vote
1answer
73 views
Proving Szemerédi's Theorem using the Simplex Removal Lemma for $k$-Uniform Hypergraphs.
Let $X$ be a set of $n$ vertices, and let $H$ be a hypergraph with vertex set £X£.
Call $H$ a $k$-uniform hypergraph if all hyperedges of $H$ are subsets of $X$ of size $k$.
Given a $k$-uniform ...
3
votes
1answer
124 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))$ ...
0
votes
1answer
44 views
Proving full rank of a special type of a (0,1,2)-integer matrices
My question arise at the consideration of Newton polytopes. In that context
I consider integer matrices $ A =(a_{ij})\in \mathbb{Z}^{(n+1) \times N} $ with $n+1 \leq N$ having the following ...
0
votes
1answer
164 views
What is the difference between matriods and hypergraphs?
Matroids have a more complicated definition but it looks to me like they might be equivalent. I would like to know exactly what the difference is, if any.
