Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let f(z)=∑_k=1^∞ a_kz^n_k be an entire function (with a_k eq 0 for all k≥ 1). Is it true that if n_k/k→ ∞ then f(z) assumes every value infinitely often?
Let G be a complete bipartite graph on 2n vertices whose edge set is decomposed into perfect matchings M_i, for i=1,…,n. Let a_1,…,a_n∈N_0 be nonnegative integers satisfying ∑_i a_i=n-1. A matching with prescribed multiplicities is a…
What are the ways of “measuring” root polytopes, i.e., edge polytopes? Furthermore, how should Grothendieck polynomials be specialized to obtain Ehrhart h^*-polynomials?
Let A be a hyperplane arrangement on P^n, with associated bundle of logarithmic vector fields T_ A. The arrangement is stably free when T_ A is infinitely stably extendable. Stable Terao conjecture. Stable freeness is combinatorially…
Let k be a node that is neither the source nor a virtual source. Let i_0, i_1, j_0, and j_1 be the quantities defined in Equations and. Let c_0 and c_1 be the two colors different from the color of k, and suppose that i_1-i_0=j_1-j_0.…
Let a graph be banned in dimension k when it has no orthogonal representation in dimension k. If a vertex of valence k in a graph banned in dimension k is doubled, then the doubling conjecture. the resulting graph is banned in dimension…
Let G be an n-vertex regular graph, and let F~ G_n,2 be a random 2-regular graph on the same vertex set as G. Here, G∪ F denotes the graph formed by adding the edges of F to G, and Hamiltonicity conjecture. With high probability, G∪ F is…
Every finite connected loopless multigraph G=(V,E) such that deg_G(v)=3 for every v∈ V has an edge partition E=E_Tmathbindot∪E_Cmathbindot∪E_M such that T=(V,E_T) is a spanning tree, C=(V_C,E_C) is a 2-regular subgraph, and M=(V,E_M) is a…
Let G be a graph of maximum degree Δ. Let E(G) denote its edge set, and let L be a list assignment assigning a set of colours L(e) to each edge e of G. An L-colouring is a proper edge-colouring in which the colour assigned to each edge e…
For which functions g(n) with n>g(n)≥ (log n)^2 is there a graph on n vertices in which every induced subgraph on g(n) vertices contains a clique of size ≥ log n and an independent set of size ≥ log n? In particular, is there such a graph…
Conjecture 3 which in turn implies
Let G be an n-vertex connected graph with chromatic number χ≥ 3. Let T_n,χ denote the complete χ-partite graph of order n whose part sizes differ by at most one. The quantity rm ABC(G) denotes the atom-bond connectivity index. The complete…
Let G be an edge-colored graph on n vertices. The total color degree of G is hat d(G)=∑_v∈ V(G)hat d(v), where hat d(v) is the number of distinct colors on edges incident with v. A rainbow matching is a matching whose edges have pairwise…
Let f(n,k) be minimal such that every family F of n-uniform sets with lvert Frvert ≥ f(n,k) contains a k-sunflower. Is it true that f(n,k) < c_k^n for some constant c_k>0?
Let G be a graph, let vecG be an orientation of G, and let tac(vecG) denote its total arc-connectivity. An orientation maximizes total arc-connectivity when it maximizes tac(vecG) among all orientations of G. Well-balanced orientation…
A graph G is nearly bipartite if every subset S⊆ V(G) has an independent set of size ⌊ |S|/2⌋. Nearly bipartite deletion conjecture. A nearly bipartite graph can be made bipartite by deleting at most 5 vertices. The source presents this as…
Let n_k be minimal such that if n_k points in R^2 are in general position then there exists a subset of k points such that all binomk3 triples determine circles of different radii. Determine n_k.
Let G be a bridgeless graph, and let Φ_G(Q) denote its flow polynomial. Welsh's conjecture. For any bridgeless graph G, Φ_G(Q)>0 for Q∈(4,∞). The conjecture parallels the Birkhoff–Lewis result for chromatic roots, but the source reports an…
Let G be a balanced bipartite graph with 2n vertices, and write δ(G) for its minimum degree. Heinig's conjecture. If n is sufficiently large and δ(G) ≥ n/2+1, then G is Hamilton-generated, meaning that its cycle space is generated by its…
Let G be a graph on n vertices. A path separating system of G is a collection of paths in G such that, for every ordered pair of distinct edges (e,f), some path contains e but not f. Balogh et al.'s conjecture. Every graph of order n…