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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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)$-...
user avatar
  • 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| = ...
user avatar
  • 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$...
user avatar
  • 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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 "...
user avatar
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)?...
user avatar
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 $...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
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 \...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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/...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 '...
user avatar
  • 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 ...
user avatar
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., ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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]$ ...
user avatar
  • 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 ...
user avatar
  • 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)$ ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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(...
user avatar
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,...
user avatar
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 ...
user avatar
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 ...
user avatar
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) ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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:...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar