Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a connected graph on n≥ 2 vertices, and let k≥ 4 be an integer. The minimum semidefinite rank rm msr(G) is the smallest rank among all positive semidefinite Hermitian matrices with graph G. The girth of G is the length of its…
Can one decide in deterministic polynomial time whether an integer n is squarefree?
Let D be the set of eight arrow directions, let Mat_n× n(D) be the set of boards, and let Sym(Mat_n× n(D)) be the group of coordinate permutations and direction permutations that preserve graph isomorphism for every board. Let R be…
Let G be a graph, and for a positive integer t let G(t) denote the graph obtained by replacing every vertex of G with an independent set of size t, with edges between replacement sets corresponding to edges of G. A graph is covered with…
Let G=(V,E) be a finite simple graph. For disjoint nonempty sets L,R⊆ V such that u,v∈ E for all u∈ L and v∈ R, write B(L,R)=u,v: u∈ L, v∈ R for the edge set of the corresponding complete bipartite subgraph of G. Call bp(G) the least k for…
The discussion concerns an o-minimal structure, a finite family of formulas Φ(x;y), distal density, and distal cell decompositions; here absx denotes the length of the object-variable tuple. The preceding results give bounds such as distal…
Let M be a matroid, and let A and B be two bases of M. A subset X of A and a subset Y of B, both of size k, form a serial symmetric exchange with respect to A and B if there is an ordering x_1,…,x_k of X and an ordering y_1,…,y_k of Y such…
For f_r(i)=r\sqrt{\log i}, let GM_{f_r} assert that every sufficiently long sequence of simple graphs G_i with |G_i|<K+f_r(i) contains i<j with G_i a minor of G_j. Conjecture: GM_{f_r} is provable in I\Delta_0+\exp for r\le2 and unprovable…
Let G be a graph, and let r_G denote the fraction of pairs of vertices of G that are connected by a Hamiltonian path. Equivalently, if G has order n, define r_G = maxfrackbinomn2 | G is k-pair strung, where G is k-pair strung when k pairs…
Let G be a graph, and let K_5-e, H_1, and H_2 be the three specified base graphs. The operations under consideration are edge addition, 1-extension, and 1-, 2- and 3-join. Recursive construction conjecture. If G is 2-connected and…
For any finite family of finite sets that is closed under taking unions, must there exist an element that belongs to at least half of the sets?
A clause-set is hitting if every two distinct clauses C,C' clash in at least one variable, that is, lvert C∩overlineC'rvert≥ 1. A clause-set is non-singular in the sense used in the paper, and its deficiency is denoted by k∈N. Two…
Let G be a graph and let z_0∈ V(G). A graph is ⟨Z_3⟩-extendable at z_0 if every pre-orientation of the edges incident with z_0 whose out-degree minus in-degree at z_0 agrees modulo 3 with a prescribed zero-sum function can be extended to…
Let G be a Hasse diagram on n vertices, and let χ(G) denote its chromatic number. Hasse-diagram chromatic number gap conjecture. There exists ε>0 such that χ(G)≤ n^1/2-ε. The paper proves a lower bound of order Ω(n^1/4) for the largest…
For positive integers N,q,a, let Q(N;q,a) be the number of perfect squares among a,a+q,…,a+(N-1)q, and let Q(N)=max_q,a≥1Q(N;q,a). Prove that Q(N)=O(√ N). In the stronger form, prove that Q(N)=Q(N;24,1) for every N>6.
Let the pairs of graphs be those constructed in Figure 1 by adding horizontally symmetric planar graphs to the leftmost and rightmost vertices of the graph shown there. The resulting graphs have identical chromatic symmetric functions.…
An adverse graph is a graph H without isolated vertices such that upsilon(H) and lambda_min(H) are integers, and, for every vertex i∈ V(H), υ(H-N_H(i))=υ(H), λ_min(H-N_H(i))=λ_min(H). Here upsilon(H) is the optimal value of the quadratic…
Let (A,B) be the (v/2)-decomposition of a periodic Golay pair PG(v) with row sums a and b. Equivalence is taken in the sense used for these decompositions. Classification conjecture. Then (A,B) is equivalent to either ([0,a],[0,b]) or…
Let G be a finite group, and let its fusion sequence denote the sequence of fusion numbers associated with the poset of Occam characteristic functions of G. Periodicity conjecture. The fusion sequence of G is periodic. This is proposed…
Fix r∈(0,1). For binary words in W(ℓ r,ℓ(1-r)), let e(ℓ,r) be the ratio of the number of UT_2(T) isoterms to the number of UT_2(T) equivalence classes. Isoterm-class ratio conjecture. The function e(ℓ,r) is monotone non-increasing in ℓ,…