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.
134
questions
1
vote
0
answers
55
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 ...
- 501
0
votes
0
answers
41
views
Reference/source of this theorem
Anyone knows the specific reference of the following result? It seems like a standard result in Hypergraph Colorings, so I suspect that it may have been proven (it could be in Extremal Finite Set ...
1
vote
0
answers
11
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)$-...
- 279
0
votes
0
answers
43
views
Minimal number of n-subsets containing each k-subset [duplicate]
Consider a finite set $X :=\{1, \cdots, m\}$. Fix two natural numbers $k, n$ such that $k < n < m$. Let $Q \subset 2^X$ be a set with the following properties:
$\forall Z \in Q$ one has $|Z| = ...
- 1,012
1
vote
1
answer
114
views
Proving that $81$ $K_4^3$'s cannot be packed in a doubled $K_{11}^3$
The sequence $T_{2,m}$ in Guy's 1967 paper A problem of Zarankiewicz describes the maximum size of a collection of $4$-subsets of $\{1,\dots,m\}$ such that every $3$-subset is in at most two of the $4$...
- 89.6k
0
votes
0
answers
20
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?
0
votes
1
answer
30
views
What is a hypergraph consisting of one edge leading from itself to itself?
Is this indeterminate? Undefined? Meaningless?
I became confused when I looked at it by starting with
$$(A \to B) \to (A \to B). \qquad\label{1}(1)$$
Since both ends of this edge are this edge, it's ...
- 4,941
4
votes
1
answer
66
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 ...
- 41
1
vote
0
answers
15
views
Proof clarification from Laszlo Lovasz' Matching Theory, "A hypergraph is balanced iff it does not contain an unbalanced odd circuit.
From the book Laszlo Lovasz' Matching Theory, beginning from page 468 (of the book, not the pdf file), there is a theorem:
Thm 12.3.2: A hypergraph is balanced iff does not contain an unbalanced odd ...
- 784
1
vote
1
answer
18
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 ...
- 784
2
votes
1
answer
60
views
Generalization of (vertex) coloring of a graph to hypergraphs
I'm wondering why is the generalization of a coloring of a graph is:
(The correct one) Assigning colors to vertices of a hypergraph so that no edge with cardinality larger or equal to 2 is ...
- 784
1
vote
1
answer
46
views
Edge cover in a regular uniform hypergraph
Let $H = (V,E)$ be a $15$-uniform hypergraph. That is, every edge contains exactly $15$ vertices. Suppose $|V| = 63$ and $|E| = 21$. Moreover, assume that every vertex is contained in exactly $5$ ...
- 1,137
0
votes
1
answer
66
views
Hypergraph vertex plus incident edge deletion giving isomorphic subgraphs
There exist hypergraphs $H = (V, E)$ such that upon the deletion of any arbitrary vertex $v \in V$ and any edge $e \in E$ that is incident to $v$ (along with all vertices in $e$), one obtains the same ...
- 41
4
votes
1
answer
35
views
(graph theory) hypergraph terminologies
I am a newbie in graph theory, and I am wondering if there are two notions that capture the following.
A set of hyperedges $\{e_i\}$ that covers all vertices in graph. Formally, for any vertex $v$ we ...
- 385
1
vote
1
answer
54
views
Generalization of graph where edges relate more than two vertices
In traditional graph theory, a graph consists of a vertex set $V$ and an edge set $E$, where the elements of $E$ are pairs of vertices from $V$. Is there a name for "graphs" where the "...
- 13
0
votes
0
answers
10
views
Multiple, parallel hyperedges
A hypergraph is a generalization of a graph in which an edge (called hyperedge) can connect any number of vertices. But does it allows also multiple, parallel hyperedges (containing the same vertices)?...
- 123
1
vote
0
answers
96
views
An interesting combinatorial property
For an integer $n$, let $[n] = \{1,\cdots,n\}$. A family $N$ of subsets of $[n]$ , i.e. $N\subset 2^{[d]}$ is said to have Property B(i,j) if the following holds:
For every $I,J\subset [n]$ such that $...
- 718
4
votes
0
answers
101
views
Are there holes in my road map from calculus to malliavin differential geometry, Bayesian hypergraphs, and causal inference?
I've constructed a directed acyclic graph that leads from introductory subjects, such as calculus (single and multivariable) to some of my current interests including causal inference, Bayesian ...
- 1,328
1
vote
2
answers
67
views
If a $3$-uniform hypergraph has ${x \choose 3}$ edges, then it has at most ${x \choose 4}$ copies of $K^3_4$
Show that if a 3-uniform hypergraph has ${x \choose 3}$ edges (for some positive real number $x$), then it has at most ${x \choose 4}$ copies of $K^3_4$
(the complete $3$-uniform hypergraph on $4$ ...
user876707
2
votes
1
answer
113
views
Proof that $|\mathscr{F}_1 \cap \mathscr{F}_2| \geq \frac{|\mathscr{F}_1| \cdot |\mathscr{F}_2|}{2^n}$
A subsets family $\mathscr{F}$ of set $\{1, 2, \ldots, n\}$ is called hereditary set if for any $A \in \mathscr{F}$ and any $B \subset A,$ $ \ B \in \mathscr{F}$.
Proof that $|\mathscr{F}_1 \cap \...
- 207
1
vote
1
answer
39
views
Minimal number of possible set packings from k-element subsets of r*k sized set
I have a question I am trying to figure out but I'm having a difficult time finding the answer.
Say I have a set $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ so that $n= r*k = |S|$ and $r=3, k=3$. I take all ...
- 11
2
votes
0
answers
41
views
Bipartite graphs that are not incidence graphs of hypergraphs
At Wikipedia one reads:
"[...] most, but not all, bipartite graphs can be regarded as
incidence graphs of hypergraphs.
I wonder which bipartite graphs can not be regarded as incidence graphs of ...
- 17.2k
1
vote
0
answers
56
views
Erdös-Renyi-like hypergraphs: threshold for connectedness
Consider an $N$-element set $X$ and a fixed number $k \ll N$.
How many $k$-element subsets $X_i$ (hyperedges) of $X$ do I have to choose (at random) such that (i) $\bigcup_i X_i = X$ and (ii) the ...
- 17.2k
1
vote
1
answer
35
views
How are hypergraphs related to voting games?
The Wikipedia page on hypergraphs says
In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory.
I have not ...
- 113
2
votes
2
answers
94
views
Fano planes probability
I have to find the threshold probability for containing a Fano plane. Since its a 3-hypergraph with 7 vertices and 7 hyperedges I was following the same approach as in:
https://math.stackexchange.com/...
- 493
5
votes
1
answer
143
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 ...
- 493
1
vote
0
answers
94
views
Proving the validity-preserving nature of certain sudoku transformations using hypergraphs
I've been making a sudoku solver to get comfortable with graphs and the following "proof" popped into my head so I wanted to see if I could actually write it. Is this argument valid? Sorry ...
- 111
2
votes
0
answers
71
views
Simple Graph Construction for Coloring in Erdős-Faber-Lovász
I am wondering whether the following construction for a simple graph for coloring in an attempt on the Erdős-Faber-Lovász conjecture is correct or has been mentioned before. The goal is to construct a ...
2
votes
0
answers
44
views
$S$ = set of all open discs in $\mathbb{R}^d$ . Show that $|S| = O((\frac1δ\log{\frac1\delta})^{d+2})$
I need to prove the following:
Let $δ > 0$ Let $P$ be a finite set of n points in $\mathbb{R}^d$.
We say that a pair of open discs $D, D'\in \mathbb{R}^d$ are $δ$-separated (with respect to P) if ...
- 31
0
votes
1
answer
51
views
For which hypergraphs $H=(V,E)$ does there exist a linear order $<$ of $V$ such that $\small\forall X,Y\in E[X\subset Y\implies \max(X)<\max(Y)]$?
I'm trying to characterise hypergraphs $H=(V,E)$ such that there exists a linear order $<$ of $V$ which satisfies $\small\forall X,Y\in E[X\subset Y\implies \max(X)<\max(Y)]$?. Are there a few '...
- 10.4k
0
votes
1
answer
60
views
Is there any such NO-answer example for Betweenness (TOP) problem?
Problem Statement
The input to a betweenness problem is a collection of ordered triples of items. The items listed in these triples should be placed into a total order, with the property that for each ...
5
votes
1
answer
252
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., ...
- 970
1
vote
0
answers
21
views
Not-matchings of a Hypergraph
I'd like to characterize the not-matchings of an hypergraph $H$, or more exactly its complements.
A not-matching is a set of edges containing at least $2$ not-disjoint edges. If $H$ is a graph this ...
- 2,995
6
votes
1
answer
140
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.
...
- 63
2
votes
1
answer
56
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,295
1
vote
0
answers
63
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 ...
- 871
2
votes
0
answers
45
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)$ ...
- 2,015
0
votes
1
answer
52
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 ...
- 645
0
votes
0
answers
114
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$ ...
- 63
0
votes
2
answers
116
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(...
- 63
3
votes
0
answers
49
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,...
- 113k
4
votes
2
answers
115
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 ...
- 454
0
votes
1
answer
42
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 ...
- 9,751
1
vote
0
answers
38
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) ...
- 67
0
votes
1
answer
38
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 ...
- 925
1
vote
1
answer
100
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 ...
- 2,015
4
votes
1
answer
162
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 ...
- 5,354
0
votes
0
answers
41
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:...
- 645
0
votes
1
answer
71
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,015
3
votes
1
answer
73
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 ...
- 9,751