# Questions tagged [hypergraph]

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

159
questions

**2**

votes

**2**answers

99 views

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

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$ we have $$A\in E_1 \text{ if and only if } f(...

**-2**

votes

**1**answer

66 views

### Infinite complete linear hypergraphs with edges of different sizes

Is there an infinite cardinal $\kappa$ with a collection of subsets ${\cal E}$ of $\kappa$ with the following properties?
$\bigcup {\cal E} = \kappa$,
$e \neq f \in {\cal E}$ implies $|e \cap f|=1$
$|...

**4**

votes

**1**answer

247 views

### Simple way to calculate the eigenvalues of a $2 \times 2 \times 2$ tensor

I am working with hypergraphs. The various matrices associated with hypergraphs are hypermatrix or tensors. I am interested in spectral aspects. In particular, I want to find all the eigenvalues ...

**3**

votes

**0**answers

38 views

### Maximum partite subset of edges of a hypergraph

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if
$\bigcup{\frak P} = X$, and
$P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$.
Let $H = (V,...

**4**

votes

**0**answers

143 views

### Does $\mathbb{R}$ have a partite subbase?

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if
$\bigcup{\frak P} = X$, and
$P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$.
Let $H = (V,...

**4**

votes

**1**answer

136 views

### Turan numbers of r-partite hypergraphs

Let $H$ be a balanced $r$-partite $r$-uniform hypergraph with $nr$ vertices. (Each part of this hypergraph consists of $n$ vertices; every hyperedge has exactly one vertex in each part.) Denote a ...

**0**

votes

**0**answers

31 views

### Does the divisor hypergraph have finite chromatic number?

A hypergraph is a pair $H=(V,E)$ where $V$ is a set and $E\subseteq{\cal P}(V)$. If $\kappa\neq\emptyset$ is a cardinal, we say that a map $c:V\to \kappa$ is a coloring of $H$ if the restriction $c|_e$...

**0**

votes

**0**answers

19 views

### VC Dimension of a range space of (X,ΔR) where (X,R) is of vc dimension d

I have a question:
Let (X , F) be a range space of bounded VC-dimension D.
Show that the range space (X , ΔF), where ΔF = {SΔS'
| S, S' ∈ F} (and Δ denotes the
symmetric set difference) has VC-...

**2**

votes

**0**answers

46 views

### 3-uniform hypergraphs and their circuit space

So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...

**0**

votes

**0**answers

27 views

### hypergraph product that preserve expansion properties

I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2.
The expansion property I am looking at is HD-random walk.
The product I am looking for is ...

**1**

vote

**0**answers

47 views

### Partitionability and colorability of hypergraphs

Motivation. If $\kappa\neq\emptyset$ is a cardinal, then a simple, undirected graph $G=(V,E)$ is $\kappa$-colorable if and only if there is a partition of $V$ into at most $\kappa$ blocks such that ...

**1**

vote

**1**answer

173 views

### Subset of $[\omega]^\omega$ that can be “colored” with $3$, but not $2$ colors

Let $[\omega]^\omega$ denote the set of infinite subsets of $\omega$.
Let $S\subseteq [\omega]^\omega$. We say that a map $c:\omega \to \{0,\ldots,n-1\}$ is a coloring for $S$ with $n$ colors if ...

**2**

votes

**0**answers

48 views

### Analog of Reed's conjecture for hypergraph

Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic number, $\Delta$ is the maximum degree, and ...

**5**

votes

**0**answers

161 views

### Cardinals realizable by the chromatic number of a regular hypergraph

For any set $X$ and cardinal $\kappa$, we denote by $[X]^\kappa$ the collection of subsets of $X$ having cardinality $\kappa$.
If $H=(V,E)$ is a hypergraph, and $\kappa$ is a cardinal, we say that a ...

**0**

votes

**1**answer

134 views

### Are hypergraphs $H=(V,E)$ with $|E|=|V|$ $2$-colorable?

A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal, such that for ...

**4**

votes

**0**answers

77 views

### Hypergraphs with only disjoint perfect matchings

Let $H(n,r)$ be the set of $r$-uniform hypergraph with $n$ vertices that have only disjoint perfect matchings (i.e. every hyperedge only appears in at most one of the perfect matchings). Let $m(h(n,r))...

**1**

vote

**1**answer

39 views

### Minimally connected hypergraphs

Let $H=(V,E)$ be a hypergraph, where $V\neq \emptyset$ is a set, and $E\subseteq {\cal P}(V)$. We say that $H$ is connected if whenever $S\subseteq V$ with $\emptyset \neq S \neq V$, there is $e\in E$ ...

**4**

votes

**1**answer

54 views

### Sizes of matchings and transversals in hypergraphs

Let $H=(V,E)$ be a hypergraph. We call $H$ proper if $E\neq\emptyset, \emptyset \notin E$ and for no $e_1\neq e_2\in E$ we have $e_1\subseteq e_2$. A matching is a set $M$ of pairwise disjoint edges (...

**0**

votes

**0**answers

11 views

### Complexity of MIS for threshold hypergraphs

Given integer positive weights $w_i$ for $[n] = \{1,\dots,n\}$ and threshold $t$, consider ALL subsets of $[n]$ of weight exactly $t$. They form a hypergraph.
What is the complexity of maximum ...

**1**

vote

**2**answers

122 views

### Clutters with no maximum-size matchings

A clutter is a pair $C=(V,E)$ where $V\neq\emptyset$ is a set, and $E\subseteq {\cal P}(V)$ such that no member of $E$ is included in another member of $E$. A matching in $C$ is a collection of ...

**3**

votes

**1**answer

48 views

### Connected hypergraphs

We say that a hypergraph $H=(V,E)$ is connected if the following condition holds:
for all $S\subseteq V$ with $\emptyset\neq S \neq V$ there is $e\in E$ that meets both $S$ and $V\setminus S$, i.e. ...

**2**

votes

**1**answer

71 views

### Chromatically rigid hypergraphs

If $H=(V,E)$ is a hypergraph and $\kappa$ is a cardinal, then $c:V\to\kappa$ is a coloring if for every $e\in E$ with $|e|>1$, the restriction $c|_e:e \to \kappa$ is non-constant. By $\chi(H)$ we ...

**1**

vote

**0**answers

40 views

### Definition of k-partite hypergraph

I would like to know the standard definition of k-partite hypergraph.
There are two natural generalizations of k-partite graph to k-partite hypergraph:
1. For all edges e, any two vertices in e are ...

**1**

vote

**1**answer

40 views

### Induced subgraphs of the line graph of a dense linear hypergraph

Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$
We ...

**0**

votes

**1**answer

46 views

### Edge coloring in dense linear hypergraphs

Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. ...

**0**

votes

**1**answer

48 views

### Dominating vertex sets in hypergraphs

Let $H=(V,E)$ be a hypergraph such that $\bigcup E = V$. For $D\subseteq V$ we set $N_D = \bigcup\{e\in E: D\cap e\neq \emptyset\}$. We say that $D\subseteq V$ is dominating if $N_D = V$.
...

**1**

vote

**0**answers

39 views

### Number of even degree subgraphs with given size in 3-uniform hypergraph clique

3-uniform hypergraph clique is a 3-uniform undirected hypergraph containing all possible hyperedges.
Even degree subgraph is a hypergraph in which all vertices have even degree.
The size of the ...

**7**

votes

**1**answer

92 views

### Independence number of $4$-uniform regular hypergraph

Let $H$ be a $4$-uniform hypergraph on $[1..n]$, i.e. $H$ is a collection of $4$-element subsets of $[1..n]$. The elements of $H$ are called edges. A hypergraph is regular if every element of $[1..n]$ ...

**0**

votes

**0**answers

81 views

### Helly vs Strong p-Helly Property of Hypergraphs

I am not clear about the difference between Helly and Strong p-Helly property. For example hypergraph
H(V, E), V = { 1,2,3 } and E = {(1,2), (2,3), (1,3)}
has non-empty set for each pair of ...

**1**

vote

**0**answers

48 views

### Minimizing the set of multiply covered elements in a linear hypergraph

We say that a hypergraph $H=(V,E)$ is a linear hypergraph if it has the following properties:
if $e_1\neq e_2\in E$ then $|e_1\cap e_2|\leq 1$, and
$\bigcup E = V$.
We say that $C\subseteq E$ is a ...

**8**

votes

**0**answers

204 views

### Does hereditary 2-coloring imply polychromatic 3-coloring for large edges?

For a hypergraph $\mathcal H=(V,\mathcal E)$, denote by $m_k$ the smallest number for which we can $k$-color any $X\subset V$ such that for any $E\in \mathcal E$ with $|E\cap X|\ge m_k$ all $k$ colors ...

**2**

votes

**1**answer

126 views

### Injective choice function for “lines” in an infinite cardinal

Let $\lambda$ be an infinite cardinal and suppose ${\cal L}$ is a collection of subsets of $\lambda$ such that
$|k| = \lambda$ for all $k\in {\cal L}$ and,
if $k_1\neq k_2\in {\cal L}$ then $|k_1\cap ...

**1**

vote

**1**answer

49 views

### Injective edge choice functions in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that
for $e\in E$ we have $|e|\geq 2$, and
if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.
An injective edge choice function of a linear ...

**5**

votes

**0**answers

61 views

### Consequences of Ramsey-numbers of hypergraphs

We know that the (2-color) Ramsey-numbers for $3$-uniform hypergraphs are between roughly $2^{n^2}$ and $2^{2^n}$, and the situation is similar to $k$-uniform hypergraphs for every $k\ge 3$. (A recent ...

**1**

vote

**2**answers

176 views

### Size of intersecting families on $\{1,\ldots,n\}$

Let $n>1$ be an integer and let $[n]=\{1,\ldots,n\}$. An intersecting family on $[n]$ is a set $E\subseteq {\cal P}([n])$ such that for all $a,b\in E$ we have $a\cap b\neq\emptyset$. It is easy to ...

**2**

votes

**0**answers

38 views

### Weighted vertex coloring of hypergraphs

Let $G=(V,E)$ be a simple graph. Let $w$ be a non-negative, integer valued weight function on the vertex set. The chromatic number $\chi(G,w)$ of the vertex-weighted graph $(G,w)$ is defined to be ...

**2**

votes

**2**answers

118 views

### Does any long path in a planar graph contain one of O(n) k-tuple of vertices?

My question is a bit related to both the container method and shallow cell complexity.
Let's start with that the number of length $\ell$ paths (where $\ell$ denotes the number of vertices of the path!)...

**6**

votes

**2**answers

198 views

### What is a hypergraph minor?

Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph ...

**4**

votes

**1**answer

186 views

### Graphs with minimum degree $\delta(G)\lt\aleph_0$

Let $G=(V,E)$ be a graph with minimum degree $\delta(G)=n\lt\aleph_0$. Does $G$ necessarily have a spanning subgraph $G'=(V,E')$ which also has minimum degree $\delta(G')=n$ and is minimal with that ...

**4**

votes

**1**answer

140 views

### Are two “perfectly dense” hypergraphs on $\mathbb{N}$ necessarily isomorphic?

We say that a hypergraph $(\mathbb{N}, E)$ where $E\subseteq {\cal P}(\mathbb N)$ is perfectly dense if
$\mathbb{N}\notin E$,
all $e\in E$ are infinite,
$e_1, e_2 \in E$ implies $|e_1\cap e_2| = 1$,...

**2**

votes

**1**answer

78 views

### $T_1$-spaces vs $T_1$-hypergraphs

Let us say that a hypergraph $H=(V,E)$ is $T_1$ if for $x\neq y$ there is $e\in E$ such that $e\cap\{x,y\} = \{x\}$.
Note that for any $T_1$-space $(X,\tau)$ the topology $\tau$ contains the ...

**0**

votes

**1**answer

44 views

### Maximizing set systems with property $\mathbf{B}$

Let $X$ be an infinite set, and let ${\cal E}$ be a collection of non-empty subsets of $X$. We say that ${\cal E}$ has property $\mathbf{B}$ if there is $B\subseteq X$ such that $B\cap E\neq \emptyset$...

**2**

votes

**0**answers

48 views

### Lower and upper (combinatorial) discrepancy

(I will state my question in terms of combinatorial discrepancy, but the same could be also asked about measure-theoretic discrepancy as well.)
The combinatorial discrepancy of a family $\mathcal F$ ...

**0**

votes

**1**answer

75 views

### Coloring a complete regular hypergraph

For any set $X$ and positive integer $k$ denote by $[X]^k$ the set of subsets $S\subseteq X$ such that $|S|=k$.
Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $...

**6**

votes

**1**answer

150 views

### Chromatic number of a connected Hausdorff space

Let $(X,\tau)$ be a topological space such that $\tau$ contains no singleton. We say that a map $c:X\to \kappa$, where $\kappa$ is a cardinal, is a coloring for $(X,\tau)$, if for every $U\in \tau\...

**2**

votes

**1**answer

48 views

### Hypergraph colorings with small fibers

Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the ...

**0**

votes

**1**answer

82 views

### Size of edge set of infinite hypergraphs with $\chi(H) = |V(G)|$

Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the ...

**5**

votes

**1**answer

117 views

### Is the category of hypergraphs cartesian-closed?

If $H_i = (V_i, E_i)$ for $i=1,2$ are hypergraphs then a map $f:V_1\to V_2$ is said to be a hypergraph homomorphism if $f(e_1)\in E_2$ for all $e_1\in E_1$. Hypergraphs together with hypergraph ...

**-1**

votes

**1**answer

77 views

### Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**1**

vote

**0**answers

31 views

### Is there an algorithm for this constrained Hypergraph optimization problem?

I'm currently developing an algorithm for computing knot coloring invariants and got to the following question:
Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...