Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For a graph G let τ(G) denote the minimal number of vertices that include at least one from each maximal clique of G (sometimes called the clique transversal number). Is it true that if all maximal cliques in G have at least cn vertices…
The well-known absolute bound (see e.g. [6]) states that the answer is at most r+1 2 , which is tight up to a multiplica- tive constant and it is a difficult open problem to determine whether there are infinitely many r for which it holds…
Let d be a positive integer and x a real number. Define the d× 2d matrix A_d,x=(a_i,j) by a_i,j= x, 1leqslant jleqslant d+1-i, 1, d+2-ileqslant jleqslant d+i, 0, d+i+1leqslant jleqslant 2d. Let R_d=(ρ_1,ρ_2,…,ρ_d)| 1leqslantρ_ileqslant…
Problem 1.9 (R. Graham). Define W ∗(k) to be the size of the smallest set X ⊆ Z such that any 2-coloring of X always has a monochromatic k-term arithmetic progression. Then, W ∗(k) ≤ W (k). For $100: Is W (k) − W ∗(k) unbounded as k → ∞?…
Given n, efficiently choose a prime power q and construct an elliptic curve E/F_q with #E(F_q)=n.
Let G be a connected graph. Here D'(G) denotes the distinguishing index of G, and OD'^-(G) denotes the negative oriented distinguishing index. Lower-bound conjecture. OD'^-(G)≥ ⌊ D'(G)/2⌋. If true, this would show that a suitable…
\begin{enumerate} \item[(a)]Is there a closed formula for the Ehrhart polynomial of order polytopes of fence posets? Further, are these Ehrhart polynomials Ehrhart positive? \item[(b)]Is the h^*-polynomial of the order polytopes from (a)…
Let a,b∈N, and let cal K(a,b) denote the complete bipartite graph with parts of sizes a and b. Two graphs are cal D-equivalent when they have the same domination polynomial. Aalipour-Hafshejani et al.'s conjecture. For all a,b∈N, if |a-b|≥…
Let G be a C_4-free cubic graph, and let DET:OLD%(G) denote the minimum density of an error-detecting open-locating-dominating set in G. DET:OLD density conjecture. DET:OLD%(G) ≤ 21/22. The bound would improve the general upper bound…
Does every Petersen-minor-free bridgeless graph have a nowhere-zero 4-flow?
Let x,y,z∈ X be three wells in a graph with equal pairwise distances a=b=c, and let c_uv denote the sum over shortest paths from u to v of the products of inverse square roots of the degrees of consecutive vertices. Assume c_xy=c_xz≠ c_yz.…
Let Γ be a trivalent maximally symmetric graph or multigraph of genus g; multigraphs may have loops or may be loopless. A graph is Brill–Noether general if, for every pair of positive integers r and d such that ρ^r_d(g)=g-(r+1)(g-d+r) is…
A configuration is a local planar-map configuration, and a configuration is Kempe state-reducible when every 3-face coloring on a state graph of its reducer is state-extendible to a 4-face coloring on some state graph of the original,…
Conjecture 6. 2 2. (Mader) If a digraph D has δ+ D ≥ r, then there are vertices x 6 = y such that λ(x, y ) ≥ r. Also, there is an edge (x, y ) so that λ(x, y ) ≥ r. The first part of this conjecture was proven by Mader [24] for λ(x, y ) ≥…
Given a graph G, its self-chromatic symmetric function is X_G^G. Two graphs are self-distinguishable when their self-chromatic symmetric functions are different. For two non-isomorphic trees T_1 and T_2, Self-distinguishability conjecture.…
Let G be a graph, let k∈Z^+, and let D be a k-optimal set, meaning a k-dependent set maximizing φ_k(D)=k|D|-|E(G[D])|. A subgraph is k-edge-chromatic if its edges can be coloured with k colours so that adjacent edges receive different…
Can every ergodic unimodular random network that is almost surely an infinite tree be obtained as the limit of an expander family?
One can start with simple problems that have already been investi- gated using other nonlocal theories, e.g., beading formulated using Eringen’s nonlocal theory. • Solving Ericksen’s open problem: Find all the constant-principal invariant…
Let τ(G) denote the relaxation time of the simple random walk on a connected regular graph G with n vertices. Aldous and Fill conjectured that, as n→∞, max_substackG connected and regular |V(G)|=nτ(G)≤ (1+o(1))3n^2/2π^2, and that…
Conjecture If A is 2-large, then A is large.