EPFL Logo
fr|en
Login
Publication

Planted matching problems on random hypergraphs

Lenka Zdeborová, Anshul Toshniwal, Gabriele Sicuro
2022
Journal paper
Abstract

We consider the problem of inferring a matching hidden in a weighted random k-hypergraph. We assume that the hyperedges' weights are random and distributed according to two different densities conditioning on the fact that they belong to the hidden matching or not. We show that for k>2 and in the large-graph-size limit, an algorithmic first-order transition in the signal strength separates a regime in which a complete recovery of the hidden matching is feasible from a regime in which partial recovery is possible. This is in contrast to the k=2 case, where the transition is known to be continuous. Finally, we consider the case of graphs presenting a mixture of edges and 3-hyperedges, interpolating between the k=2 and the k=3 cases, and we study how the transition changes from continuous to first order by tuning the relative amount of edges and hyperedges.

Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Mathematics
Related concepts (32)
Line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.
Graph labeling
In the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph G = (V, E), a vertex labelling is a function of V to a set of labels; a graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labelling is a function of E to a set of labels. In this case, the graph is called an edge-labeled graph. When the edge labels are members of an ordered set (e.
Graph embedding
In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Show more

Copyright © 2025 EPFL, all rights reserved