Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let R[n,k] denote the entry in row n and column k of the Pascal rhombus, reduced modulo 2. For n≥ 1, consider the triangle whose corners are [1,0], [2^n-1,-(2^n-1-1)], and [2^n-1,2^n-1-1]. Klostermeyer et al.'s self-similarity conjecture.…
There exists a positive integer k such that, for m and n positive integers, the conditions R(m+i)=R(n+i) (i=0,…,k-1) imply m=n.
Does every infinite connected Cayley graph admit an invariant random perfect matching?
Prove the conjecture that the EC-LCG, EC-PG, and EC-NRG sequences defined in the slides are very well distributed.
Let a ( [scale=.25] draw (1,0)--++(.5,0)--++(0,.5)--++(-1.5,0)--++(0,-.5)--++(1,0)--++(0,1)--++(-.5,0)--++(0,-1); ,n)-prismatic polyomino be a prismatic polyomino formed using the tile represented by the source's diagram and parameter n,…
Let (x_n)_n≥ 1 be any sequence of distinct points on the circle T. For each n, let M_n^(2) and m_n^(2) denote the quantities defined in the paper for two-point subsets. Sharp two-point gap conjecture. limsup_n→∞fracM_n^(2)m_n^(2)≥ 2. The…
Define the first L^2 Betti number of a vertex-transitive graph G from the expected degree of a free spanning forest. Do G and its square G^2 have the same first L^2 Betti number?
Let G be a 3-regular, 3-connected planar graph. Tait's conjecture. Every such graph is Hamiltonian. The conjecture was disproved by W. T. Tutte, who constructed a counterexample on 46 vertices; further counterexamples were found on 38…
Let N be a non-negative real number, and let A_N:=A∈bigcup_k∈N∖0M_k(R_≥ 0)~|~satisfying 1,2,3 above. Here, conditions 1, 2, and 3 are respectively that A is nilpotent, that the sum of all entries of A is N, and that every index has a…
Let H be a graph, let p∈[0,1], and let G be a graph. The property P_H,p^*(δ) means that every U⊆ V(G) satisfies c(H,G[U])=p^e(H)|U|^v(H)±δ v(G)^v(H). Let R_H,p(ε) denote the rooted quasirandomness condition defined in the paper, requiring…
What would be meant by a graph having positive curvature? (Grids don't have it; trees don't; how about spheres?)
Let u_ P(q;n) be the quasipolynomial for a piece P, and write p_i for the period of its coefficient γ_i. Coefficient-period monotonicity conjecture. The periods satisfy 1=p_0=p_1≤…≤ p_2q, and, more precisely, p_i| p_i+1. The conjecture is…
For every fixed graph H, do analogous modular equidistribution and local limit theorems hold for the number of copies of H in G(n,p)?
Break, or determine the true hardness of, the weaker security assumptions used in pairing-based cryptography.
Let V be a finite vertex set, let G be a simple graph on V, and write n=|V|. For r∈1,…,n, let t_r(n) be the number of edges in the Turán graph T(n,r). If G has at least t_r(n) edges, prove that there exists a clique x_1,…,x_r in G such…
Let G be a graph distinct from C_n, where n is odd, and suppose that its clique number satisfies ω(G)<χ(G). Here f^+(G) denotes the positive fading number of G. Positive fading number conjecture. For every such graph, f^+(G)>0. The claim…
The Builder-Blocker general position games are played on a graph, with Builder and Blocker alternately selecting vertices according to the rules defining the games; the associated decision problems ask whether Builder has a winning…
For the rotational dimension dimrot and the Colin de Verdière number μ, conjecture that dimrot(G) ≤ μ(G) for every graph G; also conjecture dimrot(G₁ ∪ G₂) ≤ max{dimrot(G₁), dimrot(G₂), |G₁ ∩ G₂| + 1} when G₁ ∩ G₂ is complete, and…
Question Given a,b≥2, what is the smallest integer t≥0 such that χ_ℓ(K_a,b+K_t)= χ(K_a,b+K_t)?
For n ≥ 1, let D(n,n) be the set of minor specifications described in the paper, and let M(S) be the associated product of minors of a positive n × n matrix A. Let x be the top-left entry of Sink(A). Square-matrix polynomial conjecture.…