Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be an Eulerian planar graph. An orientation is alternatingly in- and outward oriented at each vertex when, in the cyclic order around every vertex, its incident edges alternate between incoming and outgoing; equivalently, each facial…
Improve the bounds. Is it o(t^2)? Perhaps the lower bound is the truth. \emph{Related results:} (Phelps--R"odl) r_3(P_2, K_t) = Θ(t^2/log t). This is the same as giving the minimum independence number of a linear triple system on n points.…
Let F be a connected graph of order at least 3. An F-irregular graph is a graph in which no two distinct vertices have isomorphic F-neighbourhoods. Existence conjecture. For every connected graph F of order 3 or more, there exists a…
Let Π_q be a finite projective plane of order q, let T_r(Π_q) denote the maximum percolation time among percolating sets at infection rate r, and let r_1 and r_2 be infection rates. Percolation-time monotonicity conjecture. If r_1<r_2,…
Is the same binary quadratic Diophantine solvability problem NP-hard under randomized reductions?
What is the maximum number of edges that a graph on n vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?
Find an attack that breaks the pairing-based cryptographic system discussed in the slides, or establish its resistance to known attacks.
For a graph H on n vertices, call G ε-far from H if at least ε n^2 edge changes are required to obtain a graph isomorphic to H. A Turán graph is a complete multipartite graph whose parts are as equal in size as possible. Far-from-Turán…
It is proved that, for every δ∈(0,1), the Glauber dynamics for the uniform distribution on proper q-colorings is rapidly mixing when q≥(1+δ)Δ and the underlying graph has girth at least 5 and maximum degree Δ=Ω_δ(1). This result also…
Are the following statements true? (i) For every k\ge0 there is c such that any tournament whose every vertex has out-neighbourhood chromatic number at most k has chromatic number at most c. (ii) If H=\Delta(T_2,T_2,T_2), then for every…
Let F and G be graphs. The F-degree of a vertex v in G is the number of subgraphs of G isomorphic to F that contain v. A graph G is F-irregular if any two distinct vertices of G have different F-degrees. Existence conjecture. For every…
Let G_n be the unit distance graph in R^n, with two vertices joined by an edge if and only if the distance between them is 1. Estimate the chromatic number χ(G_n). Does it grow exponentially in n? Does lim_n→ ∞χ(G_n)^1/n exist?
Let G be a multigraph, with minimum degree δ(G) and maximum edge multiplicity μ(G). Suppose that δ(G) cannot be expressed in the form 2pμ(G)-q for any integers p and q satisfying q≥ 0 and p>μ(G)+⌊ (q-1)/2⌋. Gupta's characterization…
Let G be a graph and let T⊆ V(G) such that there is no X⊆ V(G)∖ T for which d_G(X) is an odd natural number. A system P of edge-disjoint T-paths has the required cut property when, for every t∈ T, one can choose exactly one edge from each…
Let G be a 2-edge-connected cubic graph, and let ω(G) denote its oddness, the minimum number of odd circuits in a 2-factor of G. Lukoťka–Máčajová–Mazák–Škoviera conjecture. The graph G has at least 7.5· ω(G)-5 vertices. This proposes a…
Conway : Does every thrackle have average degree at most 2? A thrackle is a drawing of a graph in the plane so that every two edges share exactly one point (whether it is an endpoint of two incident edges or a transverse crossing -- no…
Conjecture 6. 2 7. (Chudnovsky, Seymour, Sullivan) Let G be a simple digraph with k non-edges (unordered pairs {u, v } where both uv and vu are not in E(G)). If G has no directed cycle of length at most 3, one can delete at most k/ 2 edges…
A k-decomposition of the complete graph K_n is a decomposition into k spanning subgraphs G_1,…,G_k, and for a graph parameter p let p(k;K_n)=max∑_j=1^kp(G_j)| (G_1,…,G_k) is a k-decomposition of K_n. Here χ denotes chromatic number and ω…
What is the size of the smallest set A ⊂ Z/pZ (with at least two elements) for which no element in the sumset A + A has a unique representation?
Let f(z)=∑_0≤ k≤ n ε_k z^k be a random polynomial, where ε_k∈ -1,1 independently uniformly at random for 0≤ k≤ n. Is it true that, if R_n is the number of roots of f(z) in z∈ C : lvert zrvert ≤ 1, then R_n/n/2→ 1 almost surely?