MathOverflow

Questions tagged [hypergraph]

Ask Question

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

159 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
2
votes
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
0answers
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
2answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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 = ...

1
2 3 4