Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph whose vertices are colored with z and w, and let i be a vertex from which the representation is computed. The contact order is the order describing how the associated level curves approach one another near a boundary…
Conjecture Let C be a circuit in a bridgeless cubic graph G. Then there is a five cycle double cover of G such that C is a subgraph of one of these five cycles.
Conlon--Lee conjecture: for every even integer k\ge2 and every graph H, there exists \delta>0 such that ex(n,H^{k-1})=O(n^{1+1/k-\delta}).
Problem 4.7 (A. Granville and T. Tao). Suppose that G is a proper subgroup of the multiplicative group of Fp. Let A ⊂ Fp such that A + A = G or A + A is slightly larger than G. Do such A exist, and do they necessarily have structure?…
Let G be a graph, let S be a 3-subset of V(G), and let n=|V(G)|. For a set S, write ckappa(S) for the maximum number of internally disjoint trees connecting S. Li's conjecture. Given G, S, and an integer cell with 2≤ cell≤ n-2, deciding…
Let T_1(n) be the first time card 1 is seen for the nth time. Quadratic asymptotic conjecture. We have T_1(n)~ c n^2 for c≈ 0.85…. This is suggested by numerical experiments after the paper proves quadratic upper and lower bounds for…
Given a visibility graph G and a Hamiltonian circuit C, determine in polynomial time whether there is a simple polygon whose vertex visibility graph is G, and whose boundary corresponds to C.
For t=3 and a graph G, determine the minimum number of elements in a set S ⊆ V(G) so that such a propagation process covers the vertices of G.
Does there exist a family (G_n) of finite d-regular graphs with |G_n|→∞ and a constant h>0 such that every induced metric ball in every G_n has edge-expansion constant at least h?
A brace is a bipartite matching covered graph, and a graph is cycle-conformal if every even cycle C has the property that deleting its vertices leaves a graph with a perfect matching. For an integer ℓ≥ 2, an ℓ-regular graph is one in which…
Let G be a graph such that R(G,T_n)≪ n for any tree T_n on n vertices and R(G,K_n)≪ n^2. Is it true that, for any H with m edges and no isolated vertices, R(G,H)≪ m?
For each integer n≥ 4, does there exist a finite simple graph G such that G has no induced subgraph isomorphic to C_n, but, for every pair of distinct vertices u,v∈ V(G), toggling the adjacency of u and v produces a graph containing an…
Let G be a bipartite graph with independent sets C_1 and C_2, with |C_1|=c_1≤ c_2=|C_2|, as in Theorem. Let F_k(G) be the k-supertoken graph of G, and suppose that α(G)=|C_2|. The supertoken graph independence-number conjecture. The…
What does the permuton of the set of uniquely-sorted permutations look like? What about the permuton of the set of uniquely-sorted permutations that avoid a given pattern? 7. Mireille Bousquet-Mélou Does \sigman,C (uniformly random size-n…
Let G,H,G_a,G_b be graphs, let E_G⊂ E(G) and E_H⊂ E(H) be edge subsets, let T_a,T_b be spanning trees, and let S_G∈ V(G)∪ E(G) and S_H∈ V(H)∪ E(H) be proper subsets. Graph isomorphism conjectures. (i) If |E_G|=|E_H|, G-E_G≅ H-E_H, and G,H…
If an infinite graph has infinite chromatic number and a_1<a_2<… are the lengths of its odd cycles, must Σ_i 1/a_i diverge?
Let P be a convex body with baricenter at 0. Suppose that P contains no integer points in its interior besides 0. The volume of P is at most (n+1)^n/n!.
Let ρrenewcommandarraystretch1.2∈P(n) be a partition of n elements with r blocks of sizes n_1≤ n_2≤ …≤ n_r. Let K_ρ,u denote the quantity associated with the partition ρ and the uniform density, and let g^(k)(0) denote the kth derivative…
Let ex_r(n;K_r+1^r) be the maximum number of r-edges that can be placed on n vertices without forming a K_r+1^r (the r-uniform complete graph on r+1 vertices). Is every r-hypergraph G on n vertices the union of at most ex_r(n;K_r+1^r) many…
Let G be a graph with minimum degree and maximum degree . For an integer k≥ 2, let denote the second-largest eigenvalue of the adjacency matrix of G, and let be the maximum number of edge-disjoint spanning trees in G. Cioabă–Wong…