Skip to main content

Questions tagged [hypergraph]

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

Filter by
Sorted by
Tagged with
4 votes
1 answer
348 views

4-color theorem for hypergraphs

Question. Does every hypergraph that does not admit a complete minor with $5$ elements have a coloring with $4$ colors? Below are the definitions to make this precise. If $H = (V, E)$ is a hypergraph ...
Dominic van der Zypen's user avatar
1 vote
1 answer
84 views

Isomorphic hypergraph duals

Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$. We say hypergraphs $H_i=(V_i, E_i)$ for ...
Dominic van der Zypen's user avatar
2 votes
0 answers
45 views

Chromatic number of the dual hypergraph [duplicate]

Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$. If $\kappa>0$ is a cardinal, a map $...
Dominic van der Zypen's user avatar
2 votes
1 answer
92 views

"Spanning trees" for connected linear hypergraphs

Starting point. For every simple, undirected graph $G=(V,E)$ there is $E_0\subseteq E$ such that $(V,E_0)$ is minimally connected: the spanning tree. The goal of this question is to find out whether ...
Dominic van der Zypen's user avatar
3 votes
1 answer
102 views

Cardinality of splitting families

For any set $X$, let $[X]^2 = \big\{\{a,b\}:a\neq b\in X\big\}$. If $\kappa>1$ is a cardinal, then a splitting family is a collection ${\cal S} \subseteq {\cal P}(\kappa)$ such that for every $Q \...
Dominic van der Zypen's user avatar
6 votes
3 answers
227 views

Refinement-minimal intersecting covers

Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....
Dominic van der Zypen's user avatar
4 votes
1 answer
95 views

Chromatic numbers realised by almost disjoint subsets of $\omega$

If $H=(V,E)$ is a hypergraph then the chromatic number $\chi(H)$ is defined to be the least cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ with $|e| \...
Dominic van der Zypen's user avatar
2 votes
1 answer
71 views

Pseudo-partitions of $\mathbb{N}$

This question is loosely inspired by the exact cover / partition problem in computer science. Let $X\neq \emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)$. For $x\in X$ we let $c_{\cal E}(x) ...
Dominic van der Zypen's user avatar
3 votes
2 answers
121 views

Set sizes in linear set systems on $\mathbb{N}$ containing some disjoint sets

Is there a set $E\subseteq {\cal P}(\mathbb{N})$ of subsets of $\mathbb{N}$ with the following properties? $|e| > 2$ for all $e\in E$, $e_1\neq e_2 \in E$ implies $|e_1 \cap e_2| \leq 1$, for all $...
Dominic van der Zypen's user avatar
0 votes
0 answers
110 views

"Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$

$\newcommand{Po}{{\cal P}(\omega)}$ $\newcommand{lh}{\leq_{\text{hom}}}$ If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(...
Dominic van der Zypen's user avatar
1 vote
0 answers
89 views

(Hyper)Graph canonical labeling - Optimizing for subgraphs [Nauty/Traces?]

To a hypergraph, we can apply the following transformations: [Vertex Removal of Type A] Remove a specified vertex from the hypergraph. As for the edges that contained this vertex, remove all of these ...
Johann Birnick's user avatar
7 votes
0 answers
231 views

Chip firing on hypergraphs

A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...
Noah Schweber's user avatar
0 votes
0 answers
26 views

From average degree to a highly connected subhypergraph

I'm looking for a result in $k$-uniform hypergraphs analogous to the following result for graphs, due to Mader: Every graph of average degree $4r$ has a $r$-connected subgraph.
kleinbottle's user avatar
0 votes
0 answers
40 views

Minimal m such that m x K_n is decomposable into disjoint C_3

For a given $n$, is there a way to calculate the minimal value $m$ such that you can decompose the multigraph: $$m \times K_n$$ into disjoint 3-cycles? What about a more general result applied to ...
Sebastian's user avatar
  • 101
2 votes
1 answer
74 views

Finite pair-splitting family of $\mathbb{N}$

This is a kind of "dual" of an older question. Is there a finite family ${\frak F}\subseteq {\cal P}(\mathbb{N})$ such that for all $a\neq b\in\mathbb{N}$ there is $S\in{\frak F}$ with $|S\...
Dominic van der Zypen's user avatar
4 votes
1 answer
123 views

$\aleph_0$-uniform non-bipartite linear hypergraph

A hypergraph $H= (V,E)$ is said to be bipartite if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $$S\cap e\neq \emptyset\neq (e\setminus S).$$ A hypergraph is said to be ...
Dominic van der Zypen's user avatar
4 votes
1 answer
129 views

Longest paths and cycles in Steiner triple systems

A Steiner triple system is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A linear cycle (also called loose cycle) length $t$ consists of $2t$ cyclically ...
X. Li's user avatar
  • 373
4 votes
1 answer
152 views

How much can we "shrink" intersecting families

Motivation. An intersecting family is a collection of subsets ${\cal S}\subseteq {\cal P}(X)$ of a set $X\neq \emptyset$ such that $A\cap B\neq \emptyset$ for all $A,B\in {\cal S}$. The intersections ...
Dominic van der Zypen's user avatar
0 votes
0 answers
25 views

Maximum sizes of independent sets in (non-uniform) hypergraphs

It is a very well understood problem to compute the size of the maximum independent set in a uniform hypergraph (in terms of extra conditions). My question is the following: what is known for ...
Johnny Cage's user avatar
  • 1,551
0 votes
1 answer
151 views

Isomorphism of two regular hypergraphs

Consider two undirected $k$-regular hypergraphs on $n$ vertices with (see e.g. OEIS A319190). Are the two hypergraphs isomorphic if an only if the two multisets of the sizes of their respective ...
Fabius Wiesner's user avatar
1 vote
2 answers
127 views

Constants for diagonal hypergraph Ramsey Theorem

For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices. Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$ such that, for every $r$-...
Zach Hunter's user avatar
  • 3,469
2 votes
1 answer
130 views

Turán density of hypergraphs with very few edges

As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...
domotorp's user avatar
  • 18.6k
4 votes
0 answers
146 views

The monochromatic principle and the axiom of choice

For any set $A\neq\emptyset$, denote by $[A]^A$ the collection of sets $B\subseteq A$ such that there is a bijection $\varphi:B\to A$. If ${\cal S}\subseteq [A]^A$, we say that $B\in[A]^A$ is ...
Dominic van der Zypen's user avatar
10 votes
0 answers
308 views

Coloring for arithmetic progressions with 2-power difference restricted to a set of numbers

For $D \subset \mathbb N$, let $\mathbb A_D$ be the set of all arithmetic progressions with difference in $D$ (and of finite length). Let $\mathbb A_D$ be $m$-good if for every $S \subset \mathbb N$, ...
domotorp's user avatar
  • 18.6k
2 votes
1 answer
67 views

Possible chromatic numbers of a hypergraph on $\omega$ with a deck of edges

Let $\omega$ denote the first infinite ordinal (also known as the set of natural numbers). We call a set $E\subseteq {\cal P}(\omega)$ a deck if for all $n\in \omega$, the set $E$ contains exactly one ...
Dominic van der Zypen's user avatar
3 votes
2 answers
203 views

Posets such that the collection of principal down-sets does not have property ${\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|>1$ we have $S\cap e \neq \emptyset \neq e \setminus S$. Let $(P,\leq)$ be a ...
Dominic van der Zypen's user avatar
1 vote
1 answer
126 views

Counting $K_{2, 2, \,\ldots\,,2}$ in a $k$-partite $k$-uniform hypergraph

Let $G$ be a $k$-partite $k$-uniform hypergraph with at least $dn^k$ many edges. I want a lower bound on the number of $K_{2, 2,\, \ldots\,,2}$ in $G$, preferably something like $\gamma n^{2k}$ for ...
kleinbottle's user avatar
1 vote
1 answer
87 views

How to get a partite minimum co-degree in a $k$-partite $k$-uniform hypergraph?

I have a $k$-partite $k$-uniform hypergraph $H$ with $V(H) = V_1 \cup\cdots\cup V_k$ (each $|V_i|=n$ for $i \in [k]$), such that the minimum vertex degree $\delta(H) \ge Cn^{k-1}$ for a constant $C$. ...
kleinbottle's user avatar
1 vote
1 answer
59 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
  • 23k
1 vote
1 answer
130 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
57 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
63 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
54 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
  • 18.6k
8 votes
1 answer
475 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
208 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
10 votes
0 answers
185 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
  • 374
3 votes
2 answers
174 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
150 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
102 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
98 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
269 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
38 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
113 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,551
0 votes
1 answer
130 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
160 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
147 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
110 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
101 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
  • 23k
0 votes
1 answer
73 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
  • 2,079
0 votes
0 answers
47 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

1
2 3 4 5 6