Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let H_∞,∞ be the infinite truncated square tiling graph, and let δ_t,r(H_∞,∞) denote its optimal (t,r) broadcast density. Density conjecture. The optimal densities satisfy δ_4,2(H_∞,∞)≤ 9/80, δ_4,3(H_∞,∞)≤ 1/7, and δ_4,4(H_∞,∞)≤ 1/6. These…
A simplicial arrangement is a finite set of hyperplanes whose complement has only simplicial cones as connected components; in the projective-plane setting, these are arrangements of pseudolines. Two arrangements are isomorphic when they…
Let h_3(k) be the minimal n such that there exists a triangle-free graph on n vertices with chromatic number k. Find an asymptotic for h_3(k), and also prove lim_k→ ∞h_3(k+1)/h_3(k)=1.
Let L be a Latin square. A 2-transversal is the type of transversal defined in the source, consisting of entries satisfying the relevant twofold symbol condition. Rodney's conjecture. Every Latin square has a 2-transversal. The conjecture…
: A graph G is said to be uniquely H-saturated if it contains no H, but adding any edge to G creates exactly one copy of H (up to isomorphism). Clearly, if G is uniquely K_(r)-saturated, then joining a single vertex to G creates a uniquely…
Let G be a network, and call a vertex i a proper source if it has no incoming edges and is not isolated in the relevant network. An attractor is a dynamical attractor of the network, and a neuron is active in an attractor if it…
Can we prove some hardness statement about finding a coloring achieving Komlos guarantee or the Banaszczyk discrepancy guarantee?
Is there a graph of chromatic number ℵ_1 such that for all ε>0 if n is sufficiently large and H is a subgraph on n vertices then H contains an independent set of size >n^1-ε?
Let f_d(n) be minimal such that, in any set of n points in R^d, there exist at most f_d(n) pairs of points which distance 1 apart. Estimate f_d(n).
A triangle-free graph is k-existentially-complete if for every independent set A and disjoint set B with |A|+|B|\le k there is a vertex adjacent to every vertex of A and to none of B. Is there a constant r such that no triangle-free graph…
A bipartisan graph is a graph such that neither it nor its complement has an odd hole, a long prism, a double-diamond, or L(K_3,3∖ e). A quasi-parity graph is a graph in which every induced subgraph or its complement has an even pair.…
Let G=∏_i=1^t K[a_i,b_i] be a direct product of balanced complete multipartite graphs, where 2≤ b_1≤…≤ b_t and K[a_i,b_i] denotes the complete multipartite graph with b_i parts of size a_i. Write IR(G) for the upper irredundance number and…
Does there exist a set of four nonzero rational numbers a_1,a_2,a_3,a_4 such that a_i a_j+1 is a rational square for every 1≤ i,j≤4, including i=j?
Let 4S_n4 be the symmetric group on n symbols. For 4τ∈S_k4 and 4σ∈S_n4, let 4X^τ(σ)4 count the occurrences of the pattern 4τ4 in 4σ4. Call 4σ4 k-symmetric when 4X^τ(σ)=X^τ'(σ)4 for all 4τ,τ'∈S_k4. Let 4alldiv_k(n)4 mean that 4div_j(n)4…
Let G be a graph, and let P_6, G_1, and G_2 be the graphs described in Figure 5 of the source. Favaron's conjecture. If G does not contain P_6, G_1, or G_2 as induced subgraphs, then G is irredundance perfect. The conjecture was later…
Put N=2^k-1 and write wt for the binary Hamming weight. Let F_k(t) count the ordered triples (a,b,c)∈0,…,N-1^3 with a+b+c≡ t pmod N and wt(a)+wt(b)+wt(c)<k, the three-summand analogue of the two-summand count of the Tu-Deng conjecture at…
Let G be a graph of order n, let τ(G) denote its toughness, let ρ(G) denote the independence number, and let σ_3(G) be its smallest union degree of order 3: σ_3(G)= mindeg(v_1)+deg(v_2)+deg(v_3):v_1,v_2,v_3 is independent, ρ(G)≥ 3, 3(n-1),…
Given vectors v_1,...,v_n∈R^d and a norm X satisfying ∑_i=1^n v_i=0 and ||v_i||_X≤ 1 for all i. Define S_n(X,d)=min_π∈ S^nmax_k=1,...,n|| ∑_i=1^k v_π(i)||_X where S^n is the set of all permutations of [n]. Let S(X,d)=sup_n S_n(X,d). Then,…
Let J_n,m be the graph whose number of spanning trees is denoted by sigma(J_n,m), and let n,m einN with fixed n≥ 2. Define a_n,m=fracσ(J_n,m+1)σ(J_n,m). Asymptotic ratio conjecture. The limit exists: lim_m→ +∞a_n,m=δ_n, where δ_n∈R.…
Conjecture 6.3. Caccetta-H¨ aggkvist Conjecture (general case) Notes: For a digraph H, take G = H, k = d n δ+ H e, and E1 = · · · = Ek = E(H). We must get a rainbow cycle because the sum of the outdegrees at each vertex is ≥ n. This…