As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [hypergraph]

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

Filter by
Sorted by
Tagged with
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 ...
Seva's user avatar
  • 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 ...
Manfred Weis's user avatar
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 ...
Dominic van der Zypen's user avatar
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-...
TanG's user avatar
  • 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\...
Dominic van der Zypen's user avatar
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 ...
domotorp's user avatar
  • 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 ...
Dominic van der Zypen's user avatar
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\}...
Drrd's user avatar
  • 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 ...
abacaba's user avatar
  • 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 {\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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\} \...
Dominic van der Zypen's user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
The Discrete Guy's user avatar
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 ...
Johnny Cage's user avatar
  • 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 ...
Dominic van der Zypen's user avatar
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 $...
Danielle Ulrich's user avatar
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 {...
Dominic van der Zypen's user avatar
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 $...
Dominic van der Zypen's user avatar
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 ...
Seva's user avatar
  • 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 ...
vidyarthi's user avatar
  • 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 ...
Hemraj Raikwar's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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$ ...
Antoine Labelle's user avatar
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 ...
Antoine Labelle's user avatar
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\...
Dominic van der Zypen's user avatar
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 $\{...
Dominic van der Zypen's user avatar
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)...
Tri's user avatar
  • 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 $\...
Dominic van der Zypen's user avatar
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$...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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:...
Dominic van der Zypen's user avatar
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 [...
Dominic van der Zypen's user avatar
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$ ...
Dominic van der Zypen's user avatar
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$ ...
W. Paul Liu's user avatar
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 ...
Thomas's user avatar
  • 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$ ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
-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 ...
Dominic van der Zypen's user avatar
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^*$...
Dominic van der Zypen's user avatar
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 ...
te4's user avatar
  • 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|\...
Dominic van der Zypen's 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\...
Dominic van der Zypen's user avatar
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....
Dominic van der Zypen's user avatar

1
2 3 4 5 6