Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G_1 and G_2 be two 3-connected graphs, each with a triangle T_i⊂ G_i, and let G_1⊕_3G_2 be a corresponding 3-sum. Define p_i=|π_0(G_i∖ V(T_i))| to be the number of connected components remaining after deleting the triangle vertices.…
Let C_n(132,213) denote the number of cyclic compositions of n avoiding the patterns 132 and 213, and let C^B_n(132,213) denote the number of balanced cyclic compositions of n (equivalently, balanced reverse layered permutations of length…
Distinct distances and related problems (1) Let S⊂R^2 with no three points collinear. Then S determines at least |S|/2 distinct distances. (2) Given n points in R^2 with no three collinear. Then one can remove O(1)-many points so that the…
Beck-Fiala conjecture and making it constructive Given a set system (V,S) with V=[n], S=S_1,...,S_m. Each i∈ V occurs in at most t sets from S. Then there is a coloring to the elements of V achieving a discrepancy of O(√t). Koml'{o}s…
Let p(m,n) be the number of partitions of an m× n rectangle into integer-sided rectangular blocks, where partitions are identified when they consist of the same multiset of blocks, regardless of geometric arrangement. For every fixed…
Let G) be a 2-connected non-bipartite graph with minimum degree at least k+1. Liu–Ma conjecture. G contains eil k/2 cycles with consecutive odd lengths. Liu and Ma proposed this conjecture after proving the lower bound floor k/2; the…
Let H be a fullerene graph with n vertices, and let b(H) be the minimum number of edges whose removal makes H bipartite. Došlić–Vukićević explicit conjecture. b(H)≤ √12n/5. This is presented as a stronger form of the asymptotic conjecture…
Let ρ be the evaluation map used in the paper, and let i,j be nonnegative integers. Divisibility conjecture. For every i,j, the number ρ(x^i(1+x)^j) is divisible by 2^⌊ j/2 ⌋. The property is clear when j is odd, but the even case remains…
Let G be a graph with at least one edge, let L(G)=D(G)-A(G) be its combinatorial Laplacian, and define the scaled Laplacian by ρ(G):=L(G)/trL(G). For α>1, the Rényi α-entropy of G is H_α(G)=1/1-αlog_2(∑_iλ_i^α), where the λ_i are the…
Let G be a graph with chromatic number k. A biclique cover is a collection of complete bipartite graphs whose union of edges contains E(G); the order of a biclique is its number of vertices. Katona-Szemerédi-type conjecture. The sum of the…
Let r and c be odd positive integers, let a(r,c;h) denote the number of near-perfect matchings of the r× c grid with a specified hole h, and let h be an even white hole. Modulo-4 conjecture. Except sometimes when r and c are both congruent…
Let G be a graph with a circuit C, and let ω:E(G)→Z be an integer edge-weight function. A Z_2×Z_2-flow is a flow with values in the abelian group Z_2×Z_2; for such a flow h, write E_h=(0,0)(C) for the edges of C on which h has value (0,0),…
Let G be a cubic graph that admits a perfect matching. An orientable 4-weak bisection is a 4-weak bisection with the orientability property used in the source; a (31/3,1/3)-flow is the corresponding flow notion. Stronger Ban–Linial…
A triple diagram is a diagram in the paper's class, and a minimal triple diagram is one with no reducible features under the allowed simplification moves. Fix a connectivity of diagrams and let C be the 2-complex whose vertices are minimal…
Let G be an infinite Cayley graph of a group that is not virtually cyclic. Prove that there exists p<1 for which Bernoulli p-edge percolation on G has an infinite cluster.
Let G be a finite simple graph of order 2n with a perfect matching. Write e(G) for the number of edges of G, and let F(G) denote its maximum forcing number. Liu–Zhang's conjecture. The graph G satisfies e(G)≥ n^2/n-F(G), equivalently,…
For each integer k≥ 1, determine the smallest integer n≥ k such that n(n-1)(n-2)…(n-k) divides the central binomial coefficient binom2nn; equivalently, determine n_k=minn∈Z_≥ k:∏_j=0^k(n-j)|binom2nn whenever this set is nonempty.
Let S⊂Z^n be such that for all (d_1,…,d_r)∈ ([N]^n)^r, S contains the GAP (for some translate a_0) a_0+i_1d_1+… +i_rd_r: i_1,…,i_r∈ 0,1,…,k-1. Then |S|≥ N^c_kn+o_k→∞(1).
Let R_k(n) denote the number of partitions of n whose Durfee triangle has size k, and let k∈N be fixed. Asymptotic growth conjecture. As n→∞, there is a constant c_k such that R_k(n)~ c_k n^k-1. This conjecture proposes a polynomial…
For every synchronizing deterministic finite automaton A=(Q,Σ,δ) with |Q|=n, there exists a word w∈Σ^* and a state q_0∈ Q such that δ(q,w)=q_0 for every q∈ Q and |w|≤ (n-1)^2.