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 ...
- 22.2k
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 ...
- 12k
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 ...
- 42.5k
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-...
- 23
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\...
- 42.5k
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 ...
- 18k
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 ...
- 42.5k
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\}...
- 11
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 ...
- 239
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 {\...
- 42.5k
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 ...
- 42.5k
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\} \...
- 42.5k
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\...
- 42.5k
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 ...
- 42.5k
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 ...
- 1,453
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 ...
- 42.5k
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,156
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 {...
- 42.5k
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 $...
- 42.5k
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 ...
- 22.2k
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 ...
- 1,823
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 ...
- 42.5k
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 ...
- 42.5k
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 ...
- 42.5k
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$ ...
- 2,402
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 ...
- 2,402
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\...
- 42.5k
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 $\{...
- 42.5k
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,094
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 $\...
- 42.5k
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$...
- 42.5k
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 ...
- 42.5k
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 ...
- 42.5k
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 ...
- 42.5k
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 ...
- 42.5k
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:...
- 42.5k
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 [...
- 42.5k
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$ ...
- 42.5k
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$ ...
- 493
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 ...
- 2,573
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$ ...
- 42.5k
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 ...
- 42.5k
-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 ...
- 42.5k
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^*$...
- 42.5k
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 ...
- 31
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|\...
- 42.5k
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\...
- 42.5k
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....
- 42.5k