Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Problem 1: Find a class C1 of 4-uniform hypergraphs such that • the P4-structure of every graph with a 2-join belongs to C1, • no odd ring belongs to C1, • C1 belongs to NP.
Let G_n^c be the set of all connected graphs on n vertices, and let G∈G_n^c with |V|=pq. Star graph maximizer conjecture. max_G_n^c E_F(σ(G))=E_F(σ(K_1,n-1)). This asserts that the star graph maximizes the entanglement of formation among…
Let G be a graph with n vertices and kn edges, and a_1<a_2<… be the lengths of cycles in G. Is it true that ∑1/a_i≫ log k? Is the sum ∑1/a_i minimised when G is a complete bipartite graph?
Given a finite set of indivisible items M, agents N=1,…,n with positive entitlements w_i>0, and additive valuations v_i:2^M→R, does there always exist a complete allocation (A_1,…,A_n) of M such that, for every pair of agents i,j, there is…
A brick is a graph satisfying the usual matching-theoretic brick conditions, and a minimal brick is a brick minimal with respect to the relevant brick-preserving reduction. For a graph G, write V(G) for its vertex set and let |V(G)| denote…
Is the chip-firing halting problem in P for Eulerian digraphs with multiple edges?
Straus: Is every polygonal room in the plane illuminable from some point? See this.
For a graph G, let barα(G) be its maximum independent-set density. Let W be a binomial random subset of V(G), with each vertex included independently with probability 1/2, and let α^**(G)=E_W[max_I∈cal I(G)μ(I∩ W)]. For α∈(0,1/2), define…
For each integer k≥ 1, let XH^k and YH^k denote the graph families constructed in the paper. Maximality conjecture for XH^k and YH^k. The graphs XH^k and YH^k are maximal 1-planar graphs for all k≥ 1. The paper proves this only for k=1, so…
Let G be a graph such that every induced finite subgraph is perfect; call such a graph perfect in the source's infinite-graph sense. Call G strongly perfect if every induced subgraph has a partition into independent sets and a clique…
Let H be a hypergraph. A strongly maximal matching is a matching F ⊆ E(H) so that |F' ∖ F| ≤ |F ∖ F'| for every matching F'. A strongly minimal cover is a (vertex) cover X ⊆ V(H) so that |X' ∖ X| ≥ |X ∖ X'| for every cover X'. Conjecture…
Let w be a word, and let ⟨ w⟩_hare and ⟨ w⟩_tortoise denote its hare- and tortoise-fertilities. The hare–tortoise fertility comparison conjecture. ⟨ w⟩_hare≤ 2⟨ w⟩_tortoise-2. This is proposed alongside the conjectured sharp bound on the…
Beating LLL Consider a matrix where both columns are rows are t-sparse. LLL gives a discrepancy bound of O(√tlog t) here. If we assume the stronger property that every pair of rows intersect in at most one element, can we get a O(√t)?
How many congruent regular tetrahedra can touch at a point? Easy to show it's at least 20, and at most 22. Apparently, this has been open a long time.
Every finite graph G=(V,E) that is 2-tough is fractionally Hamiltonian. Here, G is 2-tough if, for every vertex set S⊆ V with c(G-S)>1, one has |S|≥ 2c(G-S), where c(G-S) denotes the number of connected components of G-S. The graph G is…
Consider n equally spaced points on a circle and write m=⌊ n/2⌋. A multiset is represented as [ℓ_1,…,ℓ_m], where ℓ_j counts chords of type j. Let M_n be the class of multisets satisfying ∑_j=1^mℓ_j=n-1. Let A_n⊆M_n be the class satisfying,…
Let G be a graph on vertex set v_1,…,v_n, and let G[H_1,…,H_n] denote the graph obtained by replacing each vertex v_i with a graph H_i and adding all edges prescribed by the edges of G. A graph is betweenness-uniform when all its vertices…
Conjecture Every 4-edge-connected graph has a nowhere-zero 3-flow.
Can we use art gallery problem results/techniques to help answer zero forcing questions and power domination questions. In particular, what about near triangulation graphs.
Let G be the straight linear k-tree with k≥ 1 and n vertices, and let H be the straight linear k-tree with n+1 vertices. Let r_G and r_H denote resistance distance in these graphs. Resistance increment conjecture.…