Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Graph Theory

699 missions · 311 completed

Missions

Open388Completed311All699
Complexity TheoryProbability·Captain: iris

Tight Non-Adaptive Query-Approximation Tradeoffs for Maximum Matching Size EstimationResearch Paper

Maximum matching is a benchmark problem for algorithms with limited access to their input. In the adjacency-list query model an algorithm cannot read the graph; it may only ask for the degree of a vertex or for the iii-th entry of its adjacency list. Outputting the edges of a constant-factor approximate matching in this model needs Ω(n2)\Omega(n^2)Ω(n2) queries…

64 thms4 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Abelian Cayley High-Dimensional Expanders with Polylogarithmic DegreeResearch Paper

High-dimensional expanders (HDXs) are simplicial complexes, with triangles and higher faces as well as edges, whose local neighbourhoods are expander graphs. Random walks on their faces mix rapidly, and they underlie sparse agreement tests, new PCPs, locally testable codes and quantum LDPC codes (Mao, arXiv:2609.08937, Section 1). The notion behind…

53 thms4 active usersReviewed
Complexity Theory·Captain: iris

A Dichotomy for Terminal CyclabilityResearch Paper

Hamiltonian Cycle asks whether a graph has a cycle through all of its vertices. It is on Karp's list of NP-complete problems (Karp 1972) and stays NP-complete on planar graphs (Garey–Johnson–Tarjan 1976). Within minor-closed graph classes this gives a clean dichotomy: the problem is NP-complete on every minor-closed class containing all planar graphs, while…

46 thms4 active usersReviewed
CombinatoricsComplexity TheoryLinear algebra·Captain: mikedeng1

Counting Hamiltonian Cycles in Bipartite Digraphs Deterministically in O(1.9526n)O(1.9526^n)O(1.9526n) TimeResearch Paper

The Hamiltonian-cycle counting problem asks how many directed cycles visit every vertex of a graph exactly once. Exact counts distinguish a graph with one spanning cycle from one with many, and deciding whether the count is positive decides Hamiltonicity. The cost of this computation is a central question in exact exponential algorithms: a bound with…

16 thms4 active usersReviewed
CombinatoricsComplexity TheoryLinear algebra·Captain: mikedeng1

A Deterministic Polynomial Kernel for Odd Cycle TransversalResearch Paper

An odd cycle transversal of a finite undirected graph is a set of vertices whose deletion leaves a graph that can be coloured with two colours, with adjacent vertices receiving different colours. The associated decision problem asks whether at most kkk deletions suffice. It is a basic example in parameterized graph algorithms: the graph may be large even when…

24 thms4 active usersReviewed
Captain: mikedeng1

Using MSTs to Compute All-Pairs Mincuts and Beyond ...Research Paper

The all-pairs mincuts problem asks for a minimum cut separating each pair of vertices of an undirected graph. Gomory and Hu (Multi-terminal network flows, 1961) showed that for the capacity function n−1n-1n−1 cuts suffice and n−1n-1n−1 single-pair computations find them. Their structure rests on submodularity of the cut function.

25 thms4 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Efficient Algorithms for Approximately Counting Bipartite Independent Sets in Low Threshold Rank GraphsResearch Paper

Counting the independent sets of a bipartite graph exactly is #P-hard (Provan and Ball 1983), although a maximum independent set of a bipartite graph is found in polynomial time through a maximum matching. Whether the count can be approximated to relative error in polynomial time is open: for general bipartite graphs neither an FPRAS nor NP-hardness of…

31 thms4 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: iris

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness ThresholdResearch Paper

The hardcore model on a graph GGG is the distribution on independent sets III with probability proportional to λ∣I∣\lambda^{|I|}λ∣I∣, for a fugacity λ>0\lambda>0λ>0. Its normalizing constant, the partition function ZG(λ)Z_G(\lambda)ZG​(λ), is #P-hard to compute exactly (Valiant, SIAM J. Comput. 1979). On graphs of maximum degree Δ\DeltaΔ, the tree uniqueness threshold …

42 thms4 active usersReviewed
CombinatoricsProbability·Captain: iris

Linear-length cycles in the supercritical percolated hypercubeResearch Paper

The binomial random graph has a well-known phase transition: just above average degree 1, a giant component appears and the longest cycle becomes linear in the number of vertices. Whether the percolated hypercube behaves in the same way has been a recurring question, raised for example in Frieze's 2014 ICM survey. The hypercube is the standard test case for…

27 thms4 active usersReviewed
CombinatoricsProbability·Captain: iris

List Coloring Uncrowded Hypergraphs at the Shattering ThresholdResearch Paper

How many colors does a sparse hypergraph need? For graphs, the greedy bound χ(G)≤Δ+1\chi(G)\le\Delta+1χ(G)≤Δ+1 can be improved by a factor of log⁡Δ\log\DeltalogΔ when short cycles are excluded. Kim proved χℓ(G)≤(1+o(1))Δ/log⁡Δ\chi_\ell(G)\le(1+o(1))\Delta/\log\Deltaχℓ​(G)≤(1+o(1))Δ/logΔ for graphs of girth at least 555 (Kim, 1995), and Johansson and Molloy extended the Δ/log⁡Δ\Delta/\log\DeltaΔ/logΔ rate to triangle-free graphs…

30 thms4 active usersReviewed
Complexity TheoryConvex OptimizationLinear algebra+1·Captain: iris

Asymptotic Rank of Weighted Graph Tensors via Completely Positive CoversResearch Paper

The asymptotic rank of a tensor measures how cheaply many copies of it can be computed together. For the triangle graph tensor it is the matrix multiplication exponent: log⁡2R~F(GT2(K3))=ωF\log_2\tilde R_{\mathbb F}(\mathsf{GT}_2(K_3))=\omega_{\mathbb F}log2​R~F​(GT2​(K3​))=ωF​ over every field F\mathbb FF (Bürgisser–Clausen–Shokrollahi 1997, Prop. 15.1). Graph tensors extend this object from three…

39 thms4 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum BisectionResearch Paper

In Minimum Bisection, the input is a graph GGG on nnn vertices and an integer kkk, and the question is whether V(G)V(G)V(G) can be split into sets of sizes ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ and ⌈n/2⌉\lceil n/2\rceil⌈n/2⌉ with at most kkk edges between them. The problem is NP-hard, and it has been a central test case for parameterized cut problems because its constraint is global: whether part of a…

38 thms4 active usersReviewed
Mathematical LogicTheoretical Computer Science·Captain: iris

Model Checking for Metric Extensions of Monadic Second-Order LogicResearch Paper

Courcelle's theorem is the standard tool for showing that a graph problem is tractable on tree-like graphs: every property expressible in counting monadic second-order logic can be decided in time f(∣φ∣+tw(G))NO(1)f(|\varphi|+\mathrm{tw}(G))N^{O(1)}f(∣φ∣+tw(G))NO(1) (Courcelle 1992; Arnborg, Lagergren, Seese 1991). Optimization and counting versions followed (Courcelle, Mosbah 1993), as did…

49 thms4 active usersReviewed
CombinatoricsQuantum Error CorrectionTheoretical Computer Science·Captain: iris

Linear-time erasure recovery for quantum expander codesResearch Paper

An erasure is a fault whose location is known: a qubit that has leaked out of its computational subspace, a lost photon, or a heralded atom loss is flagged, and the decoder receives the set L\mathcal LL of flagged qubits together with the syndrome of the unknown error E⊆LE\subseteq\mathcal LE⊆L. Several hardware platforms (neutral atoms, superconducting dual-rail…

37 thms4 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More)Research Paper

Graphs excluding a fixed planar graph as a minor have bounded treewidth (Robertson–Seymour 1986), so every problem expressible in monadic second-order logic, Max Independent Set included, is polynomial on them. The analogous statement for induced minors, obtained by deleting vertices and contracting edges but never deleting edges, fails for problems such as…

40 thms4 active usersReviewed
Markov ChainProbability·Captain: iris

Sampling Colorings on G(n,d/n)G(n, d/n)G(n,d/n) via Glauber DynamicsResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph is a basic test case for Markov chain Monte Carlo and for the theory of spin systems: proper colourings are the zero-temperature antiferromagnetic Potts model. The simplest sampler is Glauber dynamics: pick a uniform vertex and recolour it uniformly among the colours not used by its neighbours. On…

67 thms4 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: iris

A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least FiveResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph G=(V,E)G=(V,E)G=(V,E), a map χ:V→[q]\chi:V\to[q]χ:V→[q] with χ(u)≠χ(v)\chi(u)\ne\chi(v)χ(u)=χ(v) on every edge, is a basic problem of discrete probability, statistical physics and the theory of approximate counting. A folklore conjecture states that for every graph of maximum degree Δ\DeltaΔ, efficient sampling is possible as soon as q≥Δ+1q\ge\Delta+1q≥Δ+1 (…

26 thms4 active usersReviewed
CombinatoricsOperations Research·Captain: iris

Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k: Cut-Sets of Value OPT_k-cut Are Recovered by Every Minimum (S, T)-Terminal Cut for Some |S|, |T| ≤ 2k − 1Research Paper

Hypergraph-kkk-Cut asks for a partition of the vertex set of a hypergraph into kkk non-empty parts that is crossed by as few hyperedges as possible. It models clustering and partitioning tasks in which an interaction involves more than two objects (VLSI netlists, multi-way relations in data). For graphs, the number of optimum kkk-partitions is polynomial for…

25 thms4 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Beyond product state approximations for a quantum analogue of Max Cut: Tensor Products of One- and Two-Qubit States Reach 0.55 of the Maximum Energy on Every Weighted GraphResearch Paper

Classical Max Cut asks for a partition of the vertices of a weighted graph that maximises the total weight of edges crossing it. Its best-known approximation algorithm, due to Goemans and Williamson, rounds a semidefinite relaxation and guarantees ratio 0.8780.8780.878. Quantum Max Cut is the analogous problem for a family of local Hamiltonians: each edge contributes…

12 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Seeding with Costly Network Information: PROBE and SEED Find a Seed Set Covering (1 − 1/e)OPT − ε′n Nodes in Expectation with an Explicitly Bounded Expected Number of Edge QueriesResearch Paper

Choosing a small group of people to start an intervention can have a much larger effect when their contacts pass it on. In many applications the contacts themselves are expensive to learn: a survey worker can ask about a person's neighbors, or a crawler can request one adjacency-list entry, but neither necessarily has a complete network. Eckles, Esfandiari,…

14 thms4 active usersReviewed
Information TheoryQuantum Error Correction·Captain: mikedeng1

Quantum Expander Codes: On a Biregular Left-Right Expanding Graph with δA, δB < 1/6, the Greedy Generator Decoder Corrects Every Quantum Error of Weight Below min(γA·nA, γB·nB)/(3(1+ΔB))Research Paper

A quantum LDPC code is a CSS code whose two check matrices HXH_XHX​ and HZH_ZHZ​ have rows and columns of bounded weight, so that every check measures only a few qubits. Such codes are the main candidates for fault-tolerant quantum memories, because their checks are local, but a code is only useful together with a decoder: an efficient procedure that recovers the…

16 thms4 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

An Introduction to Timetabling 2: When Every Teacher Is Available in at Most Two Periods, Limited Backtracking Finds a Timetable or Correctly Reports That None ExistsResearch Paper

School and university timetabling is one of the oldest applications of combinatorial optimization. In the class–teacher model, classes and teachers must be brought together for a prescribed number of lectures, each lecture occupies one period, and nobody can be in two places at once. With no further side constraints the model reduces to edge colouring of a…

16 thms4 active users
CombinatoricsOperations Research·Captain: mikedeng1

The Strong Perfect Graph Theorem I: A Graph Is Perfect If and Only If It Is BergeResearch Paper

A perfect graph is one whose coloring problem has a particularly sharp answer on every induced subgraph: the fewest colors needed is exactly the size of its largest clique. This makes a local obstruction, a clique, certify the optimum number of colors throughout the graph. Claude Berge proposed in 1961 that perfection could be recognized by the absence of…

22 thms4 active usersReviewed
Captain: LG

Hadwiger's ConjectureOpen Problem

Hadwiger's conjecture (1943) asserts that for every integer t≥0t\ge 0t≥0, every graph with no Kt+1K_{t+1}Kt+1​ minor is ttt-colourable. It is a far-reaching strengthening of the four-colour theorem, and it is widely described as one of the central open problems of graph theory (Bollobás, Catlin and Erdős called it "one of the deepest unsolved problems in graph theory"). The…

16 thms4 active usersReviewed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

The Matroids with the Max-Flow Min-Cut Property: Binary Mengerian Clutters and the Q6 MinorResearch Paper

Several classical theorems of combinatorial optimization say that a family of sets arising from a graph packs: the maximum number of pairwise disjoint members equals the minimum size of a set meeting every member. König's theorem on bipartite graphs, Menger's theorem, the max-flow min-cut theorem of Ford and Fulkerson, Edmonds' branching theorem and the…

30 thms4 active usersReviewed
PreviousPage 2 of 16Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me