# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
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
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
43 views

• 718
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
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$ ...
113 views

• 113k
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
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
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
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
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
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