Questions tagged [hypergraph]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
31 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\...
user avatar
1 vote
1 answer
134 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 $\{...
user avatar
4 votes
1 answer
100 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)...
user avatar
  • 1,064
2 votes
1 answer
37 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 $\...
user avatar
1 vote
1 answer
57 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$...
user avatar
3 votes
0 answers
161 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 ...
user avatar
0 votes
1 answer
41 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 ...
user avatar
3 votes
0 answers
174 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 ...
user avatar
1 vote
1 answer
196 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 ...
user avatar
1 vote
1 answer
117 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:...
user avatar
1 vote
2 answers
67 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 [...
user avatar
2 votes
2 answers
74 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$ ...
user avatar
4 votes
0 answers
60 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$ ...
user avatar
2 votes
1 answer
110 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 ...
user avatar
  • 2,265
0 votes
1 answer
50 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$ ...
user avatar
1 vote
1 answer
104 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 ...
user avatar
-1 votes
1 answer
70 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 ...
user avatar
1 vote
1 answer
74 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^*$...
user avatar
2 votes
0 answers
44 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 ...
user avatar
0 votes
1 answer
39 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|\...
user avatar
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\...
user avatar
1 vote
1 answer
82 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....
user avatar
1 vote
2 answers
242 views

"Coloring" the greatest common divisor relation

Let $N_+$ denote the set of positive integers. Let $E$ be the collection of all finite $A\subseteq \mathbb{N}_+$ such that $|A|\geq 3$ and $\min(A)$ is the greatest common divisor of $A\setminus\{\min(...
user avatar
2 votes
0 answers
86 views

Shrinking a hypergraph to a graph with identical chromatic number

Let $H=(V,E)$ be a hypergraph. A coloring is a map $c:V\to \kappa$ where $\kappa\neq \emptyset$ is a cardinal, and the restriction $c\restriction_e:e\to \kappa$ is non-constant for every $e\in E$ with ...
user avatar
3 votes
1 answer
68 views

Turán density of an unbalanced complete $r$-partite $r$-graph

In a survey by Füredi and Simonovits called "The history of degenerate (bipartite) extremal graph problems," Theorem 10.5 states the following: Let $\mathcal K = K^{(r)}(a_1, \dots, a_r)$ ...
user avatar
3 votes
0 answers
61 views

On a connectivity property of set systems

Let $X\neq \emptyset$ be a set and let ${\cal A}\subseteq {\cal P}(X)$ with $\bigcup {\cal A}=X$. We say that $S\subseteq X$ is indivisible if for all $T\subseteq S$ with $\emptyset \neq T \neq S$ ...
user avatar
3 votes
1 answer
122 views

Coloring the uncountable Lebesgue-measurable sets of $\mathbb{R}$

A hypergraph $H=(V,E)$ consists of a set $V$ and $E\subseteq {\mathcal P}(V)$, that is, $E$ consists of subsets of $V$ of arbitrary size. Obviously, a graph is a special kind of hypergraph. Let $H=(V,...
user avatar
15 votes
2 answers
703 views

n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that: (1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$; (2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...
user avatar
  • 161
3 votes
0 answers
88 views

When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?

This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...
user avatar
  • 143
7 votes
1 answer
578 views

Strategies for bounding the spectral norm of a tensor?

Let $A$ be a symmetric $k$-tensor over a real or complex vector field $W$. We may define its spectral norm $|A|$ by $$|A| = \sup_{v\in W} \frac{|\langle A,x^{\otimes k}\rangle|}{|x|_2^k}.$$ (...
user avatar
  • 16.7k
3 votes
0 answers
123 views

Spectral norm and "operator norm" for hypergraphs

Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency ...
user avatar
  • 16.7k
4 votes
3 answers
305 views

Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
user avatar
4 votes
1 answer
178 views

Seven Bridges of Königsberg for hypergraphs

I am teaching a course involving hypergraphs. I would like to have a physical analogy/motivating problem for hypergraphs similarly to how the Seven Bridges of Königsberg motivate graphs. Can you help ...
user avatar
  • 41
3 votes
1 answer
254 views

Chromatic number of maximal linear $k$-regular hypergraphs on $\omega$

For any integer $k>1$ we say a hypergraph $H=(\omega,E)$ where $E\subseteq {\cal P}(\omega)$ is $k$-regular if $|e|=k$ for all $e\in E$. Moreover, we say $H$ is linear if $|e_1\cap e_2|\leq 1$ for ...
user avatar
1 vote
1 answer
88 views

Fano-like planes on $\omega$

We call $E\subseteq {\cal P}(\omega)$ a Fano-like plane if for all $x,y\in \omega$ there is $e\in E$ with $\{x,y\}\subseteq e$, whenever $e_1\neq e_2\in E$ we have $|e_1\cap e_2|=1$, and $|e|>1$ ...
user avatar
6 votes
1 answer
105 views

Tameable hypergraphs

Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$. We say that $H$ is tameable if every independent set is contained in a maximal ...
user avatar
2 votes
1 answer
130 views

Chromatic number of rainbow hypergraphs

Let $H=(V,E)$ be a hypergraph, and $\kappa$ be a cardinal. We say that a map $c:V \to \kappa$ is a coloring if the restriction $c\restriction_e$ is non-constant whenever $e\in E$ and $|e|\geq 2$. The ...
user avatar
1 vote
1 answer
83 views

Minimizing the set of monochromatic edges

For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$. Let $H = (V,E)$ be a hypergraph such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a ...
user avatar
7 votes
0 answers
85 views

What is known about chromatic polynomial of hypergraph at $-1$

Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
user avatar
4 votes
0 answers
161 views

The list reaping number?

My question is inspired by a question of Dominic van der Zypen. Let $[\omega]^\omega$ denote the set of all infinite subsets of $\omega$. The reaping number, denoted by $\mathfrak r$, is the minimum ...
user avatar
  • 8,573
3 votes
1 answer
165 views

A sequence of cardinal characteristics constructed with hypergraph coloring

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. 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: ...
user avatar
1 vote
0 answers
58 views

Generalization of Moore graphs -- not geometries

I was thinking about the following problem: Suppose you have a $k$-uniform hyper graph (simplicial complex of dimension $k$) with a complete $(k-1)$-skeleton, and some form of regularity (e.g. every ...
user avatar
  • 433
5 votes
2 answers
233 views

Triangle coloring in random graph

Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that ...
user avatar
  • 491
3 votes
1 answer
72 views

Injective choice function for finite Fano planes

Let $H=(V,E)$ be a hypergraph that is a finite Fano plane, that is, $V$ is a finite set and $E$ has the following properties: for $e_1\neq e_2\in E$ we have $|e_1|=|e_2|$, as well as $|e_1\cap e_2|=1$...
user avatar
3 votes
1 answer
314 views

VC dimension of vector spaces

Does the collection of all subspaces of a fixed finite-dimensional vector space have bounded VC dimension? Could someone please provide references for this question?
user avatar
  • 397
4 votes
2 answers
201 views

Relationship between minimum vertex cover and matching width

Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in E(H)\}$). Question: Is $\...
user avatar
  • 1,461
3 votes
1 answer
108 views

Can every number be realised as the chromatic number of a countable hypergraph?

If $H=(V,E)$ is a hypergraph and $\kappa$ is a cardinal,we say a map $c:V\to\kappa$ is a coloring if the restriction $c\restriction_e$ of $c$ to $e$ is non-constant whenever $e\in E$ and $|e|>1$. ...
user avatar
6 votes
1 answer
264 views

Singular cardinal $\kappa$ with projective plane such that all edges have cardinality $<\kappa$

Is there an infinite singular cardinal $\kappa$ such that there is a set $E\subseteq{\cal P}(\kappa)$ with the following properties? $|e| < \kappa$ for all $e\in E$, whenever $\alpha\neq\beta\in \...
user avatar
0 votes
1 answer
42 views

Non-pencil infinite projective plane with edges of different cardinalities

A projective plane is a hypergraph $H=(V,E)$ such that if $e_1\neq e_2 \in E$ then $|e_1\cap e_2| = 1$, and for $v,w\in V$ there is $e\in E$ such that $\{v,w\}\subseteq e$. Is there a projective ...
user avatar
1 vote
0 answers
60 views

$1$-factorizability for linear hypergraphs with infinite edges on $\omega$

Let $H=(V,E)$ be a hypergraph. We say that $M\subseteq E$ is a matching if the members of $M$ are pairwise disjoint, and $M$ is said to be perfect if $\bigcup M = E$. Moreover, $H$ is $1$-factorizable ...
user avatar

1
2 3 4 5