Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let R(G;k) denote the minimal m such that if the edges of K_m are k-coloured then there is a monochromatic copy of G. Determine R(K_s,t;k) where K_s,t is the complete bipartite graph with s vertices in one component and t in the other.
Does there exist a real constant c>0 such that, for all sufficiently large integers n, every graph G on n vertices with at least (1/8-c)n^2 edges contains either a copy of K_4 or an independent set of size at least n/log n? Equivalently,…
Graham: For every non-equilateral triangle T, show that it is possible to color the plane with three colors so that there is no monochromatic (congruent) copy of T.
Let G_1 and G_2 be connected graphs of the same genus g, and let Σ_g be the genus-g surface. Suppose that G_1 and G_2 have embeddings into Σ_g such that their corresponding dual graphs are isomorphic as multigraphs. Higher-genus dual…
Let L_s^(i), for i∈1,2, be the edge-resistance quantities defined in the paper, and let num(x) denote the numerator of the maximally reduced fractional representation of x. Let gcd denote the greatest common divisor. Common-factor…
Let G=(V,E) be a graph with bounded degrees. Write dist(x,y) for graph distance and define the open ball B(x,r)=y∈ Vcolon dist(x,y)<r. Here CD(0,∞) denotes the discrete Bakry–Émery curvature-dimension condition. Non-negative curvature…
Let r_k(N) be the largest possible size of a subset of 1,…,N that does not contain any non-trivial k-term arithmetic progression. Prove an asymptotic formula for r_k(N).
Classify the complete area-minimizing intrinsic graphs in the sub-Riemannian Heisenberg group H^1, in particular determine whether the known classification of complete stable area-stationary intrinsic graphs extends to all complete…
Let G be a graph that is quasi-isometric to a nonamenable Cayley graph. The quasi-isometric non-Liouville conjecture. The graph G is not Liouville. The source presents this as a question for general graphs and notes that the Liouville…
Let G be a connected graph containing a swap set. Let DD_m(G) denote the minimum size of a disjoint dominating set whose two parts are joined by a perfect matching, and let α(G) be the independence number of G. Disjoint-domination…
Let G=(S,T;E) be a bipartite graph, with weights w:E → [0,1]. A proper weighted edge colouring is a colouring of the edges such that at each vertex, the sum of weights of edges of the same colour is at most 1. A lower bound for the number…
For each n, let S_n be the symmetric group, and let z_I(S_n), z_I I(S_n), and z(S_n) denote respectively the proportions of character-table zeros of type I, of type II, and of all zeros in the character table of S_n. Existence conjecture.…
Let P be a 3M-DAP that is not a 0-problem, and let P' be the smaller 3M-DAP obtained from P by one application of the recursive algorithm. Let g(P) denote the size of the smallest piece in the solution produced by that algorithm. Recursive…
Let a pure graph G (or its parity class [G]) be primitive when, for every family F of pure classes, [G]∈overlineF implies [G]∈F. A pure graph is prime when it has no non-trivial decomposition of the type considered in the paper. The…
Let G be a family of graphs. It is stable if there exist positive constants δ=δ( G), γ=γ( G), and n( G) such that, for every graph G∈ G with at least n( G) vertices and m edges, a positive fraction of all subgraphs of G with (1-δ)m edges…
Consider the formal product F(t,x,z):=∏_j=0^∞(1-tx^j)^z-1. (a) If z=2 then on the one hand we get Euler's F(t,x,2)=∑_n≥0frac(-1)^nx^binomn2(x;x)_nt^n, on the other we get Pólya's formula (here the "cycle index decomposition", see Stanley's…
Let P be a set of n points in the plane, and let there be m topological trees such that every pair of trees intersects exactly once and every leaf of every tree belongs to P. Strengthened thrackle conjecture. We conjecture that m≤ n. This…
Conjecture 4. For each graph H there is c(H) > 0 such that every induced H-free graph on n vertices contains a clique or independent set of size at least nc . It is well-known that polynomial versions of theorems of Rödl and Nikiforov, as…
Let E_1,…,E_n be pairwise non isogeneous elliptic curves with modular invariants j(E_h). For h=1,…,n, let ω_1h,ω_2h be a pair of fundamental periods of wp_h with η_1h,η_2h the associated quasi-periods, P_ih points on E_h(C) and p_ih (resp.…
For a graph G and a positive integer N, let S(G;N)=S(G,c)| c:V(G)→ Z^+ with c(G)=N. Here S(G,c) is the set of sums c(H)=∑_v∈ V(H)c(v) over connected subgraphs H of G. Lo's conjecture. For any two non-isomorphic connected graphs G_1 and G_2…