# Questions tagged [hypergraph]

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

225 questions
Filter by
Sorted by
Tagged with
31 views

100 views

1 vote
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$...
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
117 views

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$ ...
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$ ...
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 ...
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$ ...
1 vote
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 ...
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 ...
1 vote
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^*$...
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 ...
39 views

1 vote
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....
1 vote
242 views

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 ...
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 ...
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}.$$ (...
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 ...
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 ...
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 ...
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 ...
1 vote
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$ ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
165 views

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: ... 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 ... 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 ... 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$... 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? 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$\...
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$. ...