# Questions tagged [hypergraph]

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

253
questions

1
vote

1
answer

28
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 ...

0
votes

0
answers

16
views

### Name for a specific kind of regular hyper graphs

Question:
is there already an established name for the following kind of hypergaphs:
given a set $\mathfrak{V}$ with $n\lt\infty$ elements
the hyper vertices $\mathfrak{v}\subseteq \mathfrak{V}$ are ...

1
vote

1
answer

106
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

44
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

56
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

51
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

458
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

170
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\}...

9
votes

0
answers

149
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

151
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

143
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

93
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

96
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

118
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

29
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

94
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

127
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

152
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

143
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

107
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

95
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

41
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

39
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 ...

0
votes

1
answer

55
views

### Choice sets in hypergraphs with finite edges

Let $H=(V,E)$ be a hypergraph. We say that $C\subseteq V$ is a choice set if $|C\cap e| = 1$ for all $e\in E$.
Question. Let $H=(V,E)$ be a hypergraph with $e$ finite for all $e\in E$, and suppose ...

0
votes

1
answer

49
views

### Hypergraphs such that all finite subhypergraphs are bipartite

The starting point of this question is the following true statement for graphs:
A simple, undirected graph $G = (V,E)$ is bipartite if and only if for all $E_0\subseteq E$ the graph $(V, E_0)$ is ...

1
vote

1
answer

88
views

### Hypergraphs with finite matching / covering balance

Let $H=(V,E)$ be a hypergraph such that $\emptyset\notin E$. We say that $C\subseteq V$ is a (vertex) cover if for all $e \in E$ we have $C\cap e\neq \emptyset$. The minimum size that a cover can have ...

1
vote

1
answer

123
views

### Discrepancy of random bipartite graphs (2)

This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...

3
votes

1
answer

166
views

### Discrepancy of random bipartite graphs

This is a crosspost from MathStackExchange (original question).
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 ...

0
votes

0
answers

62
views

### Cutsets and disjoint edge sets in graphs

If $H=(V,E)$ is a hypergraph then we say that $C\subseteq V$ is a cutset if $C\cap e \neq \emptyset$ for all $e\in E$. We set
$$\text{cut}(H) = \min\{|C|: C \text{ is a cutset of }H\}.$$ A subset $D\...

1
vote

1
answer

154
views

### "Lamp-switch set-up number" of $n$ [closed]

Motivation. The following has a real-life (!) inspiration from a discussion about how to connect lamps and switches in an efficient way.
Question. Let $n\in\mathbb{N}$ be a positive integer and let $\{...

4
votes

1
answer

121
views

### Strongly minimal covers for clique hypergraphs of graphs

$\DeclareMathOperator\Cliq{Cliq}$A hypergraph $H$ is a pair consisting of a set $V$ of vertices and a family of subsets of $V$ called edges.
One class of examples is obtained by taking a graph $G=(V,E)...

1
vote

1
answer

51
views

### Maximal matchable set in hypergraph with finite edges

Let $H=(V,E)$ be a hypergraph. A set $M\subseteq E$ consisting of mutually disjoint members of $E$ is said to be a matching. We say $S\subseteq V$ is matchable if there is a matching $M$ such that $\...

1
vote

1
answer

68
views

### Edge sets on $\omega$ maximal with respect to chromatic number

If $H=(V,E)$ is a hypergraph, and $\kappa \neq \emptyset$ is a cardinal, a map $c: V\to \kappa$ is said to be a coloring if the restriction $c|_e: e\to \kappa$ is non-constant whenever $e\in E$ and $e$...

3
votes

0
answers

179
views

### Conjecture on connected hypergraphs

A hypergraph $H=(V,E)$ with $V$ non-empty is said to be connected if for all $S\subseteq V$ with $\emptyset \neq S \neq V$ there is $e\in E$ such that $e$ intersects both $S$ and $V\setminus S$.
Given ...

0
votes

1
answer

44
views

### Conflict-free coloring of linear hypergraphs on $\omega$

This question is motivated by considerations on conflict-free colorings, which arose while studying assignment problems for frequencies in cellular networks.
A hypergraph $H=(V,E)$ is said to be ...

3
votes

0
answers

202
views

### A form of Hadwiger's conjecture for hypergraphs

A hypergraph $H=(V,E)$ consists of a
set $V$ and $E\subseteq {\mathcal P}(V)$. If $S\subseteq V$, we define
$$E|_S = \{e\cap S: (e\in E) \land (e\cap S \neq \emptyset)\}$$
and call $(S, E|_S)$ the ...

1
vote

1
answer

203
views

### Chromatic number of duals of uniform hypergraphs with large edges

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say that $H$ is $\kappa$-uniform if $|e|=\kappa$ for all $e\in E$.
If $X$ is a non-empty set, then a map $c:V\to X$ is said to be a ...

1
vote

1
answer

124
views

### Chromatic number and taking duals of hypergraphs

If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, then a map $c:V\to \kappa$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e:...

1
vote

2
answers

80
views

### Number of edges in $k$-uniform linear hypergraph

Let $3 \leq k < n \in \mathbb{N}$. By $[n]^k$ we denote the collection of the subsets of $n = \{0,\ldots,n-1\}$ that have size $k$. We say that a hypergraph $H=(n,E)$ is $k$-uniform if $E\subseteq [...

2
votes

2
answers

82
views

### Matching number in infinite hypergraphs

If $H= (V,E)$ is a hypergraph, a matching is a set $M\subseteq E$ such that $e_1\cap e_2 = \emptyset$ whenever $e_1\neq e_2 \in M$. The matching number $\mu(H)$ of a hypergraph $H=(V,E)$ with $V$ ...

5
votes

0
answers

81
views

### Chromatic index of hypergraphs

A proper $k$-edge-coloring of a hypergraph $H$ is a mapping from $E(H)$ to a set of $k$ colors so that every pair of adjacent edges receives different colors. We say $H$ is $k$-edge-colorable if
$H$ ...

2
votes

1
answer

134
views

### 3-uniform tetrahedron-free hypergraph on seven vertices

My problem concerns 3-uniform hypergraphs. Let $f(n)$ be the maximal number of edges in a 3-uniform hypergraph such that no four edges form a "tetrahedron", i.e., four edges that join the ...

0
votes

1
answer

52
views

### Are strongly complete regular linear hypergraphs on $\omega$ isomorphic?

This is a related question to an older one.
If $H_i = (V_i, E_i)$ are hypergraphs for $i=1,2$ then we say they are isomorphic if there is a bijection $f: V_1 \to V_2$ such that for $A \subseteq V_1$ ...

2
votes

1
answer

110
views

### Cardinalities of maximal linear $k$-subsets of $n = \{0,\ldots,n-1\}$

We consider any non-negative integer $n$ as a cardinal, so $0 = \emptyset$, and $n=\{0,\ldots,n-1\}$ for positive $n$. Given $n,k\in \mathbb{N}$, let $[n]^k$ denote the collection of $k$-element ...

-1
votes

1
answer

75
views

### Chromatic number of $(n, [n]^k)$

If $n\in\mathbb{N}$ is a non-negative integer, we consider it as a cardinal, so $n = \{0, \ldots, n-1\}$. If $X$ is a set, and $\kappa$ is a cardinal, we let $[X]^\kappa$ be the collection of subsets ...

1
vote

1
answer

84
views

### Self-dual hypergraph on $\omega$

Let $H=(V,E)$ be a hypergraph. For $v\in V$ we let $v^* = \{e\in E:v\in e\}$. We define the dual of $H$ by $H^*= (E, V^*)$ where $V^* = \{v^*: v\in V\}$. We say that a $H$ is self-dual if $H \cong H^*$...

2
votes

0
answers

60
views

### Number of nonisomorphic weighted hypergraphs of certain type

Let $G=(V,E)$ be an unlabeled simple hypergraph with weighted vertices and given properties:
$|v|⩾max(d(v);\;3)\;∀v∈V$, where $|v|$ denotes weight of vertice $v$ and $d(v):=\#(e:\;v∈e)$ - number of ...

0
votes

1
answer

44
views

### Discrepancy of chromatic number and independent covering number for $k$-regular hypergraphs

If $H=(V,E)$ is a hypergraph and $\kappa \neq \emptyset$ is a cardinal, then a map $c:V\to\kappa$ is called a coloring if the restriction $c\restriction_e$ is non-constant for all $e\in E$ with $|e|\...

2
votes

1
answer

45
views

### Summable hypergraphs

A hypergraph $H=(V,E)$ is sane if $V$ is finite, $E \neq \emptyset$, and $\emptyset \notin E$, and $e\not\subseteq e'$ whenever $e\neq e' \in E$. Moreover, we call $H$ summable if there is a map $f:V\...

1
vote

1
answer

88
views

### Large chromatic number in hypergraphs with large edges

Let $H=(V,E)$ be a hypergraph. If $\kappa \neq \emptyset$ is a cardinal, we call a map $c:V\to \kappa$ a coloring if for each $e\in E$ with $|e|>1$ the restriction $c\restriction_e$ is non-constant....