# Questions tagged [hypergraph]

Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.

280
questions

4
votes

1
answer

348
views

### 4-color theorem for hypergraphs

Question. Does every hypergraph that does not admit a complete minor with $5$ elements have a coloring with $4$ colors?
Below are the definitions to make this precise.
If $H = (V, E)$ is a hypergraph ...

1
vote

1
answer

84
views

### Isomorphic hypergraph duals

Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
We say hypergraphs $H_i=(V_i, E_i)$ for ...

2
votes

0
answers

45
views

### Chromatic number of the dual hypergraph [duplicate]

Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
If $\kappa>0$ is a cardinal, a map $...

2
votes

1
answer

92
views

### "Spanning trees" for connected linear hypergraphs

Starting point. For every simple, undirected graph $G=(V,E)$ there is $E_0\subseteq E$ such that $(V,E_0)$ is minimally connected: the spanning tree. The goal of this question is to find out whether ...

3
votes

1
answer

102
views

### Cardinality of splitting families

For any set $X$, let $[X]^2 = \big\{\{a,b\}:a\neq b\in X\big\}$. If $\kappa>1$ is a cardinal, then a splitting family is a collection ${\cal S} \subseteq {\cal P}(\kappa)$ such that for every $Q \...

6
votes

3
answers

227
views

### Refinement-minimal intersecting covers

Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....

4
votes

1
answer

95
views

### Chromatic numbers realised by almost disjoint subsets of $\omega$

If $H=(V,E)$ is a hypergraph then the chromatic number $\chi(H)$ is defined to be the least cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ with $|e| \...

2
votes

1
answer

71
views

### Pseudo-partitions of $\mathbb{N}$

This question is loosely inspired by the exact cover / partition problem in computer science.
Let $X\neq \emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)$. For $x\in X$ we let $c_{\cal E}(x) ...

3
votes

2
answers

121
views

### Set sizes in linear set systems on $\mathbb{N}$ containing some disjoint sets

Is there a set $E\subseteq {\cal P}(\mathbb{N})$ of subsets of $\mathbb{N}$ with the following properties?
$|e| > 2$ for all $e\in E$,
$e_1\neq e_2 \in E$ implies $|e_1 \cap e_2| \leq 1$,
for all $...

0
votes

0
answers

110
views

### "Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$

$\newcommand{Po}{{\cal P}(\omega)}$
$\newcommand{lh}{\leq_{\text{hom}}}$
If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(...

1
vote

0
answers

89
views

### (Hyper)Graph canonical labeling - Optimizing for subgraphs [Nauty/Traces?]

To a hypergraph, we can apply the following transformations:
[Vertex Removal of Type A] Remove a specified vertex from the hypergraph. As for the edges that contained this vertex, remove all of these ...

7
votes

0
answers

231
views

### Chip firing on hypergraphs

A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...

0
votes

0
answers

26
views

### From average degree to a highly connected subhypergraph

I'm looking for a result in $k$-uniform hypergraphs analogous to the following result for graphs, due to Mader:
Every graph of average degree $4r$ has a $r$-connected subgraph.

0
votes

0
answers

40
views

### Minimal m such that m x K_n is decomposable into disjoint C_3

For a given $n$, is there a way to calculate the minimal value $m$ such that you can decompose the multigraph:
$$m \times K_n$$
into disjoint 3-cycles?
What about a more general result applied to ...

2
votes

1
answer

74
views

### Finite pair-splitting family of $\mathbb{N}$

This is a kind of "dual" of an older question.
Is there a finite family ${\frak F}\subseteq {\cal P}(\mathbb{N})$ such that for all $a\neq b\in\mathbb{N}$ there is $S\in{\frak F}$ with $|S\...

4
votes

1
answer

123
views

### $\aleph_0$-uniform non-bipartite linear hypergraph

A hypergraph $H= (V,E)$ is said to be bipartite if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $$S\cap e\neq \emptyset\neq (e\setminus S).$$ A hypergraph is said to be ...

4
votes

1
answer

129
views

### Longest paths and cycles in Steiner triple systems

A Steiner triple system is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A linear cycle (also called loose cycle) length $t$ consists
of $2t$ cyclically ...

4
votes

1
answer

152
views

### How much can we "shrink" intersecting families

Motivation. An intersecting family is a collection of subsets ${\cal S}\subseteq {\cal P}(X)$ of a set $X\neq \emptyset$ such that $A\cap B\neq \emptyset$ for all $A,B\in {\cal S}$. The intersections ...

0
votes

0
answers

25
views

### Maximum sizes of independent sets in (non-uniform) hypergraphs

It is a very well understood problem to compute the size of the maximum independent set in a uniform hypergraph (in terms of extra conditions).
My question is the following: what is known for ...

0
votes

1
answer

151
views

### Isomorphism of two regular hypergraphs

Consider two undirected $k$-regular hypergraphs on $n$ vertices with (see e.g. OEIS A319190). Are the two hypergraphs isomorphic if an only if the two multisets of the sizes of their respective ...

1
vote

2
answers

127
views

### Constants for diagonal hypergraph Ramsey Theorem

For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices.
Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$ such that, for every $r$-...

2
votes

1
answer

130
views

### Turán density of hypergraphs with very few edges

As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...

4
votes

0
answers

146
views

### The monochromatic principle and the axiom of choice

For any set $A\neq\emptyset$, denote by $[A]^A$ the collection of sets $B\subseteq A$ such that there is a bijection $\varphi:B\to A$. If ${\cal S}\subseteq [A]^A$, we say that $B\in[A]^A$ is ...

10
votes

0
answers

308
views

### Coloring for arithmetic progressions with 2-power difference restricted to a set of numbers

For $D \subset \mathbb N$, let $\mathbb A_D$ be the set of all arithmetic progressions with difference in $D$ (and of finite length).
Let $\mathbb A_D$ be $m$-good if for every $S \subset \mathbb N$, ...

2
votes

1
answer

67
views

### Possible chromatic numbers of a hypergraph on $\omega$ with a deck of edges

Let $\omega$ denote the first infinite ordinal (also known as the set of natural numbers). We call a set $E\subseteq {\cal P}(\omega)$ a deck if for all $n\in \omega$, the set $E$ contains exactly one ...

3
votes

2
answers

203
views

### Posets such that the collection of principal down-sets does not have property ${\bf B}$

We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $S\cap e \neq \emptyset \neq e \setminus S$.
Let $(P,\leq)$ be a ...

1
vote

1
answer

126
views

### Counting $K_{2, 2, \,\ldots\,,2}$ in a $k$-partite $k$-uniform hypergraph

Let $G$ be a $k$-partite $k$-uniform hypergraph with at least $dn^k$ many edges. I want a lower bound on the number of $K_{2, 2,\, \ldots\,,2}$ in $G$, preferably something like $\gamma n^{2k}$ for ...

1
vote

1
answer

87
views

### How to get a partite minimum co-degree in a $k$-partite $k$-uniform hypergraph?

I have a $k$-partite $k$-uniform hypergraph $H$ with $V(H) = V_1 \cup\cdots\cup V_k$ (each $|V_i|=n$ for $i \in [k]$), such that the minimum vertex degree $\delta(H) \ge Cn^{k-1}$ for a constant $C$. ...

1
vote

1
answer

59
views

### The vertex-covering number of a particular hypergraph

$\newcommand{\cM}{{\mathcal M}}$
For an integer $n>0$, let $\cM_n$ denote the set of all matrices with three rows and $n$ columns such that every column is obtained by permitting the coordinates ...

1
vote

1
answer

130
views

### Is the chromatic number of hypergraphs downward continuous?

Let $H=(V,E)$ be a hypergraph. The chromatic number $\chi(H)$ is the smallest cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ having more than one ...

0
votes

0
answers

57
views

### Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph

This is about graph theory.
Define an h-dimensional hyperedge as a set that contains h vertices.
A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...

1
vote

1
answer

63
views

### Uniform hypergraphs with small edge intersections and propery ${\bf B}$

We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|\geq 2$ we have $$(e\cap S) \neq \emptyset \neq (e\cap (V\setminus S)).$$
If $k\...

1
vote

0
answers

54
views

### Chromatic number of 2-graph vs hypergraph of point-line incidences

Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic.
Given a finite set of points $P$ in ...

8
votes

1
answer

475
views

### Scheduling "parent talks" at school

Real life motivation. In my younger son's class, there are $18$ students. His teacher provided $18$ time slots for the parents of each child to have a 30-minute conversation of their kid's progress in ...

1
vote

0
answers

208
views

### Question related to Kahn-Kalai conjecture

I am interested whether the statement of Kahn-Kalai conjecture (proved by Jinyoung Park and Huy Tuan Pham in '22) can be strengthened to the question about Boolean functions $f : 2^{[1, n]}\to \{0, 1\}...

10
votes

0
answers

185
views

### Number of triangle-free graphs with prescribed number of edges

This question is posted from StackExchange since it received no answer there.
Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...

3
votes

2
answers

174
views

### Property ${\bf B}$ for families of large sets with small intersection

Let $\kappa\geq \aleph_0$ be a cardinal. If $X\neq \emptyset$ is a set, we say that a family ${\cal C}\subseteq {\cal P}(X)$ has property ${\bf B}$ if there is $S\subseteq X$ such that for all $C\in {\...

3
votes

1
answer

150
views

### Cycling through a general combinatorial design on $\omega$

This is a generalisation of an older question inspired by a football tournament (which does not have an answer yet).
Let $\frak P$ be a partition of $\omega$ into blocks, that is, pairwise disjoint ...

1
vote

0
answers

102
views

### On a combinatorial design inspired by a football (soccer) tournament

Real-world inspiration. My younger son was playing a micro football (soccer) tournament this afternoon with $3$ other friends. Let's label the $4$ kids $0,1,2,3$. They played $3$ matches:
$\{0,1\} \...

3
votes

1
answer

98
views

### Property $\mathbf{B}$ for maximal linear set systems on $\omega$ with finite members

Let $X\neq\emptyset$ be a set. A family ${\cal S}\subseteq {\cal P}(X)$ has property $\mathbf{B}$ if there is $T\subseteq X$ such that for all $S\in{\cal S}$ we have $S\cap T\neq \emptyset$ and $S\not\...

2
votes

1
answer

269
views

### De Bruijn–Erdős theorem for hypergraphs

The De Bruijn–Erdős theorem states that when all finite subgraphs of a graph $G$ can be colored with $n$ colors, the same is true for the whole graph.
There is a natural notion of coloring for ...

1
vote

0
answers

38
views

### Associating a matroid to a uniform hypergraph

For a fixed ground set $[n]=\{1,\ldots,n\}$, and for any matroid $M$ on $[n]$, specified as a collection of bases $B_M$, the corresponding matroid basis polytope $P_M$ is defined to be the convex hull ...

3
votes

0
answers

113
views

### Arithmetic progressions and removal lemmas for graphs in arithmetic combinatorics

As it is well known, one can gets a proof of Roth's Theorem concerning arithmetic progressions of length 3 (APs for short) by using the celebrated Ruzsa-Szemerédi triangle removal lemma for graphs.
In ...

0
votes

1
answer

130
views

### Are $k$-regular linear set systems vertex-transitive?

For any integer $k\geq 2$, a $k$-regular linear set system is a set ${\cal E}\subseteq {\cal P}(\omega)$ such that $|e| = k$ for all $e\in {\cal E}$, and moreover, for all $a\neq b\in\omega$ there is ...

4
votes

0
answers

160
views

### Invariant Spaces of Hypergraphs

The following arose from a question in model theory (specifically in the model theory of modules).
Fix an arity $k$. Let $[\mathbb{Q}]^k$ denote the set of all subsets of $\mathbb{Q}$ of cardinality $...

2
votes

4
answers

147
views

### $k$-regular linear set systems

For any set $X$ and cardinal $\kappa$, we denote by
$\ [X]^\kappa :=\ \binom X\kappa\ $ the collection of subsets of $X$ having cardinality $\kappa$.
If $X$ is a set, we call a set system $E\subseteq {...

1
vote

1
answer

110
views

### Flat linear set systems

Let $X\neq \emptyset$ be a set. We say $E\subseteq {\cal P}(X)$ is a linear set system if for all $a\neq b\in X$ there is exactly one $e\in E$ with $\{a,b\}\subseteq e$.
Is there an infinite cardinal $...

4
votes

0
answers

101
views

### Visiting zero-sum triples in a vector space

Is it true that for any set $A\subset\mathbb F_5^n$ satisfying $A\cap(-A)=\varnothing$, there is a subset $A'\subseteq A$ such any triple $(a,b,c)\in A\times A\times A$ with $a+b+c=0$ has exactly one ...

0
votes

1
answer

73
views

### Line graphs of complete hypergraphs as complement of Kneser graphs

Since the Johnson graph/triangular graph $J(n,2)$ is the complement of the Kneser graph $K(n,2)$, which is also incidentally the line graph of the complete graph $K_n$, I thought whether the same can ...

0
votes

0
answers

47
views

### Can we talk about approximation when the decision problem for solution existence is NP-Hard

I am wishing to design an approximation algorithm for an optimization problem where the existence of solution for corresponding decision problem is not guaranteed. Is it wise to find an approximation ...