Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A graph is 2K_2-free if it has no induced subgraph consisting of two independent edges, and it is t-tough if |S|≥ t c(G-S) whenever deletion of S leaves at least two components. A graph is hamiltonian if it has a spanning cycle. Mou and…
Let g(n) be maximal such that in any set of n points in R^2 with no four points on a line there exists a subset on g(n) points with no three points on a line. Estimate g(n).
Let Perm(n) be the permutahedron graph, and let i_k(G) denote the minimum edge-expansion among subsets of G of size k. Set k=6^n+1/3. Edge-isoperimetric conjecture for the permutahedron. i_k(Perm(n))=n+1/3-1. This conjecture asserts that…
Let G ~ G(n,m) with m ≥ ω(n), is it true with high probability that the crossing number cr(G) ≥ Ω(m^2)?
Let D=(V,E) be a directed graph that is the union of two disjoint directed spanning trees. Can we characterize when does D have a directed spanning tree T ⊆ E such that E-T is also a directed spanning tree and reversing the orientation of…
Develop the higher-dimensional analogue of the nondegenerate-curve Frobenius-lift method.
Black-hole stability conjecture: do sufficiently small perturbations of sub-extremal Kerr initial data for the vacuum Einstein equations evolve toward a nearby Kerr black hole?
Let G be any graph, with b(G) its bondage number and Δ(G) its maximum degree. Teschner's conjecture. b(G)leqslant3/2Δ(G). The source notes that equality is attained by Cartesian products K_n× K_n, and presents the universal upper bound as…
Let G be an n-vertex graph, and let V_G(λ) denote the variance parameter of the hard-core model on G at fugacity λ. Write K_m for the complete graph on m vertices, and let Δ be the maximum degree of G. Davies et al.'s variance conjecture.…
Let a_1=1 and a_n=a_n-1^2+a_n-1 for n≥ 2. For an arithmetical structure on the star graph S_n or the complete graph K_n, its critical group is a finite abelian group; a cyclic critical group is one isomorphic to Z/mZ for some positive…
Let G be a graph, and let r_K_s(t_1,t_2) denote the minimum number of copies of K_s in a graph that is (t_1,t_2)-Ramsey. Let r(t_1,t_2) be the Ramsey number, the smallest n such that K_n is (t_1,t_2)-Ramsey. Off-diagonal F-Ramsey…
In this minicourse, we discuss recent results, obtained in joint work of the speaker with various collaborators, on the following problem: Problem 1. Let G be a finite almost quasisimple group, g \in G r Z(G). (A) Find an explicit, and as…
Let k≥3 and let p be a prime satisfying p≡1pmodk. Write Θ(G) for the Shannon capacity of a graph G, and let Paley_k(F_p) be the generalized Paley graph over F_p. Paley Shannon-capacity conjecture. There exist constants a_k,b_k>0 such that,…
Let [n]=1,2,…,n, and let F be a family of graphs on [n]. Two-component-intersection conjecture. If the intersection of any two graphs in F has at most two components, then |F|≤ n+1/2^n· 2^binomn2. The proposed extremal example consists of…
Let T be a rooted tree, let v be a vertex of T, let u be its parent, let w be a rooted tree grafted at v, and let S and S' be the rooted trees defined by removing everything above v and taking the subtree rooted at v, respectively. Let…
A cycle cover of a graph is a collection of cycles covering every edge. The depth of an edge in a cycle cover is the number of cycles containing it, and the depth of the cover is the maximum edge depth. A shortest cycle cover is one of…
Let K_4 be the complete graph on four vertices, and let a subdivision be a graph obtained by replacing edges by paths. A graph is SPN if it is the sum of a positive semidefinite matrix and a nonnegative matrix. Subdivision conjecture for…
Let G be a graph with a list assignment L to the edges of G. For every edge e=uv, define its permissible colour list by L(e)=max1,…,maxdeg(u),deg(v)+1. An L-edge-colouring assigns to each edge a colour from its list so that incident edges…
Let T be a regular tournament on n vertices, where n is odd. A collection of directed triangles is pairwise edge-disjoint if no directed edge belongs to more than one triangle. Akaria–Yuster's conjecture. Every regular tournament T on n…
Let f(n,k) be such that every graph on n vertices and k edges can be partitioned into at most f(n,k) edge-disjoint complete graphs. Estimate f(n,k) for k>n^2/4.