Questions tagged [hypergraph]

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

Filter by
Sorted by
Tagged with
44 votes
15 answers
28k views

What are the applications of hypergraphs?

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
35 votes
3 answers
3k views

Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?

Question Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
Chris Beck's user avatar
20 votes
3 answers
968 views

Does the hypergraph of subgroups determine a group?

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
Dominic van der Zypen's user avatar
15 votes
2 answers
883 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 ...
X. Li's user avatar
  • 373
13 votes
1 answer
3k views

Is there a version of König's theorem for tripartite 3-graphs?

I would like to know if there exists a version of König's theorem for tripartite $3$-graphs. In other words, let $G = (V,T)$ be a tripartite $3$-graph. That is, $V$ is a set of vertices (with $V$ ...
tbg's user avatar
  • 131
12 votes
5 answers
563 views

Intersecting 4-sets

Is it possible to have more than $N = \binom{\lfloor n/2\rfloor}{2}$ subsets of an $n$-set, each of size 4, such that each two of them intersect in 0 or 2 elements? To see that $N$ is achievable, ...
Brendan McKay's user avatar
10 votes
2 answers
902 views

The category of hypergraphs as a topos

It seems known that the category of hypergraphs is a topos. I am looking for any reference here, or just a statement of this in the literature, but can't find anything. There is one paper A ...
Oliver Kullmann's user avatar
10 votes
1 answer
595 views

Are shift-chains two-colorable?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$. For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$. A $k$-uniform hypergraph ${\...
domotorp's user avatar
  • 18.3k
10 votes
0 answers
306 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.3k
10 votes
0 answers
183 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
  • 364
9 votes
3 answers
379 views

Class of hypergraphs that are always the neighborhood hypergraph of some simple graph

Let $G=(V,E)$ be a graph. Its (open) neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a hyperedge for the (open) neighborhood of every vertex $v \in V$. It seems that not ...
Juho's user avatar
  • 717
9 votes
2 answers
2k views

A generalization of Boolean matrix multiplication for order-3 tensors

The Boolean matrix product of two 0-1 $n \times n$ matrices $A$ and $B$ is the matrix $C$ defined as $$C[i,j] = \vee_{k=1}^n (A[i,k] \wedge B[k,j]).$$ If $A = B$ and the matrix is an adjacency matrix ...
Ryan Williams's user avatar
8 votes
2 answers
1k views

Motivation for Frankl's conjecture?

Frankl's conjecture, open since 1979, says that if $F$ is a union-closed family of subsets of $X$, then there is some $x \in X$ such that $x$ appears in at least half the sets in $F$. What was the ...
Felix Goldberg's user avatar
8 votes
1 answer
304 views

A generalization of Erdős-Ko-Rado theorem

Is there any result known about the following generalization of the Erdős-Ko-Rado theorem? Let $n, k, r, s$ be positive integers. We call a family $\mathcal{F}$ of $k$-element subsets of $\{1,\ldots, ...
123...'s user avatar
  • 663
8 votes
1 answer
692 views

Edge chromatic number of hypergraphs

This is question Selection problem in a collection of non-empty sets with a simplification in criterion 3. Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\...
Dominic van der Zypen's user avatar
8 votes
1 answer
473 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
8 votes
0 answers
262 views

Does hereditary 2-coloring imply polychromatic 3-coloring for large edges?

For a hypergraph $\mathcal H=(V,\mathcal E)$, denote by $m_k$ the smallest number for which we can $k$-color any $X\subset V$ such that for any $E\in \mathcal E$ with $|E\cap X|\ge m_k$ all $k$ colors ...
domotorp's user avatar
  • 18.3k
8 votes
0 answers
2k views

What is the best lower bound for the domination number in regular graphs of girth 5?

The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]): Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ ...
Florent Foucaud's user avatar
8 votes
0 answers
1k views

Simplicial Representations of (Hyper)Graph Complexes

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, ...
Gwyn Whieldon's user avatar
7 votes
2 answers
378 views

Infinite projective plane with small edges

Let $\kappa$ be an infinite cardinal. We say $E\subseteq {\cal P}(\kappa)$ is an infinite projective plane on $\kappa$ if $e_1\neq e_2\in E$ implies $|e_1\cap e_2| = 1$, and whenever $n\neq m\in \...
Dominic van der Zypen's user avatar
7 votes
2 answers
538 views

Perfect matchings in certain classes of hypergraphs

While doing research I came unto the following problem: Given a hypergraph $H$ which is $r$-partite, $r$-uniform (each edge contains exactly $r$ vertices), $k$-regular (each vertex is contained in ...
Pedro T. Lima's user avatar
7 votes
1 answer
944 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}.$$ (...
H A Helfgott's user avatar
  • 19.3k
7 votes
1 answer
128 views

Independence number of $4$-uniform regular hypergraph

Let $H$ be a $4$-uniform hypergraph on $[1..n]$, i.e. $H$ is a collection of $4$-element subsets of $[1..n]$. The elements of $H$ are called edges. A hypergraph is regular if every element of $[1..n]$ ...
LeechLattice's user avatar
  • 9,421
7 votes
1 answer
179 views

Is there a Degenerate Dependency Local Lemma?

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded. Here I ask whether another possible generalization (for which I could not yet ...
domotorp's user avatar
  • 18.3k
7 votes
2 answers
311 views

Perfect matchings of a regular, uniform, partite hypergraph

This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...
theGrolarBear's user avatar
7 votes
1 answer
687 views

Perfect matching in a vertex-transitive hypergraph

In connection with this MO problem, I wonder whether the hypergraph in question was actually vertex-transitive. And so, as a natural variation (and, perhaps, a refinement): If the vertex set of a ...
Seva's user avatar
  • 22.8k
7 votes
0 answers
223 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
7 votes
0 answers
93 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 ...
John Machacek's user avatar
6 votes
3 answers
450 views

Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

I can. But my proof uses a theorem (which I do not reveal yet to avoid influencing you) and it feels like an overkill, so I wonder if there is a simple proof. Now the problem. Suppose we have a ...
domotorp's user avatar
  • 18.3k
6 votes
3 answers
329 views

Bipartiteness criterion

A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for hypergraphs? (A hypergraph is called bipartite if its vertices can be colored in two colors so that ...
Seva's user avatar
  • 22.8k
6 votes
1 answer
282 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 \...
Dominic van der Zypen's user avatar
6 votes
1 answer
183 views

Chromatic number of a connected Hausdorff space

Let $(X,\tau)$ be a topological space such that $\tau$ contains no singleton. We say that a map $c:X\to \kappa$, where $\kappa$ is a cardinal, is a coloring for $(X,\tau)$, if for every $U\in \tau\...
Dominic van der Zypen's user avatar
6 votes
1 answer
347 views

Ramsey type theorem

Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$. Is the following true? For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...
Jiayi Liu's user avatar
  • 909
6 votes
1 answer
502 views

Complexity for calculating number of Perfect Matchings in k-regular hypergraph

Let $G(V,E)$ be a unweighted, k-regular hypergraph, with vertices $V=(v_1, ... v_n)$ and edges $E=(e_1, ... e_m)$. The k-regularity leads to $|e_i|=k$ (i.e. every edge contains exactly $k$ vertices). ...
Mario Krenn's user avatar
6 votes
1 answer
315 views

Realiziability of hypergraphs as link (multi)sets of ordinary graphs

I have a question about hypergraphs that I hope some combinatorics/graph theory experts can answer. The motivation for this question is group-theoretic and comes from the study of a certain space of ...
Ilya Kapovich's user avatar
6 votes
1 answer
109 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 ...
Dominic van der Zypen's user avatar
6 votes
1 answer
391 views

Is an $O(n^{d-1})$ bound known for the maximum number of edges in an ordered $n$-vertex hypergraph avoiding a fixed $d$-permutation hypergraph?

By a $d$-permutation hypergraph, I mean, for some fixed integer $k$, a $d$-uniform hypergraph on $[dk]$ with $k$ disjoint edges such that every edge has exactly one vertex from each of $\{1,\ldots,k\}$...
Benjamin Gunby's user avatar
6 votes
1 answer
2k views

Maximum bipartite graph (1,n) "matching"

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out ...
Karussell's user avatar
  • 161
6 votes
2 answers
507 views

What is a hypergraph minor?

Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph ...
domotorp's user avatar
  • 18.3k
6 votes
1 answer
223 views

A non-distinct system of representative edges

I have the following problem: Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs on the same vertex set. I would like to find a "system of representative edges" $ f : \mathcal{G} \...
julkiewicz's user avatar
6 votes
0 answers
209 views

Hopf algebra interpretation of hypergraph duality?

The work of Aguiar and Ardila (https://arxiv.org/abs/1709.07504) on Hopf monoids for generalized permutohedra gives a Hopf monoid structure on the collection of hypergraphs; see sections 19 and 20 of ...
Sam Hopkins's user avatar
  • 22.7k
6 votes
0 answers
128 views

Edge-coloring number of a linear hypergraph

A linear hypergraph is a hypergraph $H=(V,E)$ such that $|e|\geq 2$ for all $e\in E$, $|e_1\cap e_2|\leq 1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$. An edge coloring of $H$ is a function $c:E\to ...
Dominic van der Zypen's user avatar
6 votes
0 answers
300 views

A maximum discrepancy hypergraph 2-colouring problem

This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now. The setup is as follows. We have a vertex set partitioned in to sets $V_1,\...
Andrew D. King's user avatar
6 votes
0 answers
849 views

Cliques of hyperedges

Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...
Dave Pritchard's user avatar
5 votes
1 answer
263 views

Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?

What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable? Thanks in advance.
TCS-user-23's user avatar
5 votes
1 answer
1k views

Hypergraph Chromatic Number vs Degree, Clique-Size

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...
Dave Pritchard's user avatar
5 votes
1 answer
194 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 ...
sensei's user avatar
  • 51
5 votes
1 answer
201 views

Is the category of hypergraphs cartesian-closed?

If $H_i = (V_i, E_i)$ for $i=1,2$ are hypergraphs then a map $f:V_1\to V_2$ is said to be a hypergraph homomorphism if $f(e_1)\in E_2$ for all $e_1\in E_1$. Hypergraphs together with hypergraph ...
Dominic van der Zypen's user avatar
5 votes
2 answers
925 views

Helm's improvement to Beck-Fiala theorem

Beck-Fiala theorem states that if $X$ is a finite set and $H$ is any family of subsets of $X$, in which every vertex occurs in at most $d$ sets of $H$, then there is a function $f\colon X\to\{1,-1\}$ ...
Boris Bukh's user avatar
  • 7,746
5 votes
1 answer
203 views

A set-family game

Two players, Green and Red, play a zero-sum game. It is parametrized by two integers $n\geq 0, k\geq 0$, and a finite family $F$ of sets of size $n$ (each set may appear multiple times in $F$). Each ...
Erel Segal-Halevi's user avatar

1
2 3 4 5 6