Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let f(n) be the minimum number of colours in an edge-colouring of K_n for which every copy of K_4 receives at least five distinct colours. Is f(n)~frac56n?
Let G be a graph, let m≥ 1 and k≥ 2, and let w be an m-weighting of G. A k-clique independent set is a set I of vertices such that every k-clique of G contains exactly one vertex of I. An m-weighting w' is uniform on I when the weights…
Let K_m,n be the complete bipartite graph with m≥ n≥ 2, and let ub(G) denote the unit bar visibility number of a graph G. Asymptotic unit bar visibility conjecture. For m≥ n≥ 2, ub(K_m,n)=frac m4+o(m). This conjecture asserts that the…
Develop a fast algorithm to compute the Tate–Lichtenbaum pairing T_n.
Let G be a graph, and let k be an integer such that G has treewidth at most k and connectivity at least k. A vertex set inducing a graph of treewidth at most k-1 and connectivity at least k-1 is denoted by T, and an independent set is…
Let L_n be the lexicographically least binary order-n de Bruijn sequence, formed by concatenating all Lyndon words of length dividing n in lexicographic order. For a word w, define its discrepancy by disc(w)=max_M|∑_k=0^M(-1)^w_k|.…
Conjecture 6.7. Any simple digraph with no loops or digons has a vertex v such that |N +2 (v)| + |N+(v)| ≥ 2 min( |N −(v)|, |N +(v)|).
Hadwiger’s Conjecture is widely considered among the most important problems in graph theory and has motivated numerous developments in graph coloring and graph minor theory. Recent Progress on Hadwiger’s Conjecture Luke Postle (joint work…
Let G be a graph and let v be any specified vertex of G. A collection of spanning trees of G is independent spanning trees rooted at v if, for every vertex u, the paths from v to u in the trees are pairwise internally vertex-disjoint. A…
Conjecture Let D be a digraph all of whose strong components are nontrivial. Then D contains a cyclic spanning subdigraph with cyclomatic number at most α(D).
Entropy proof of Sidorenko There is a proof system for graph homomorphism inequalities using flag algebras. Define a proof system for graph homomorphism inequalities using entropy.
For a point set P in R^d, let f_d(P) be the number of unit-distance point pairs: f_d(P) = | (u,v) | u, v ∈ P, |u-v| = 1 | ; and let f_d(n) be the maximum over all sets of n points: f_d(n) = max_|P| = n f_d(P) . Further, let g_d(P) denote…
Every Latin square of order n has a partial transversal of size n-1, and if n is odd it has a transversal.
Let G be a 3-edge-connected graph. Its Frank number f(G) is the minimum number of orientations needed so that every edge is deletable in at least one of them. Frank-number conjecture. Every 3-edge-connected graph G satisfies f(G)≤ 3. The…
An n-dimensional augmented cube is a graph in which each vertex is represented by an n-bit binary string, with adjacency defined according to the augmented-cube construction. A Hamiltonian decomposition is a collection of ⌊ n/2⌋ pairwise…
Let B be a board, let G(B) be its rook equivalence graph, and suppose that B_1,B_2 is an edge of G(B). For a nonnegative integer k, consider the placements of k rooks on B_1 and on B_2. Explicit rook-placement bijection conjecture. There…
Let M_r be the 2^r × 2^r integer matrix whose rows and columns are indexed by all maps f_j: [r] → [2], with (i,j)-entry binom|f_i^-1(1) ∩ f_j^-1(1)|2 + binom|f_i^-1(2) ∩ f_j^-1(2)|2. Positive-semidefiniteness conjecture. M_r is positive…
Let M(n,m) be the set of n× m nonnegative integer matrices with every row and column sum equal to m and n, respectively, as in the paper, and let T(n,m)=A∈ M(n,m)| A~ A^ T, where A~ B means that A can be transformed into B by row and…
For each fixed positive integer ℓ divisible by 3, determine the minimum semidegree that forces an n-vertex oriented graph, for all sufficiently large n, to contain a directed cycle of length ℓ, without requiring the cycle to contain a…
Let K_a,b be a bidirectional complete bipartite graph with all edges of equal weight, where a>b. Let A and B be its partite sets, with |A|=a and |B|=b. For vertices u∈ A and v∈ B, write ept_rzf(K_a,b, x ) for the expected randomized…