Math problems solved by AI

Graph Theory, Independence Polynomials

A graph on $n$ vertices is very well-covered if every maximal independent set has size $n/2$. Levit and Mandrescu conjectured that the independence polynomial $i(G,x)$ of every very well-covered graph is unimodal, i.e. its coefficient sequence is nondecreasing and then nonincreasing.

Combinatorial Optimization

For single-source unsplittable flow, every fractional flow can be rounded to an unsplittable flow whose cost is no higher than the fractional cost, while each arc's load is exceeded by at most the maximum demand. (The cost version of Goemans' unsplittable-flow conjecture.)

Algebraic Geometry

For a projective variety $X$ with at worst Gorenstein canonical singularities whose stringy $E$-function $E_{\mathrm{st}}(X; u, v)$ is a polynomial, all stringy Hodge numbers $h^{p,q}_{\mathrm{st}}(X)$ are non-negative. (Batyrev 1998, Conjecture 3.10.)

Algebraic Geometry

Every polynomial map $\mathbb{C}^n \to \mathbb{C}^n$ with constant nonzero Jacobian determinant is invertible, with a polynomial inverse.

Optimization (Oracle Complexity)

For deterministically minimizing a convex 1-Lipschitz function on the $d$-dimensional ball using only exact function values, the query complexity sat between $\Omega(d)$ and $O(d^2 \log^2 d)$ since 1996. The paper proves a near-quadratic lower bound $\Omega(d^2 / \log(d+1))$, closing the gap: $Q(d, \sim d^{-1/2}) = \Theta(d^2)$, a polynomial separation from full first-order information.

Algebraic Geometry

Grothendieck asked whether every finite locally free group scheme of order $n$ is killed by $n$ (its $n$-th convolution power map equals the unit). The counterexample is an order-4 group scheme not killed by 4 (killed only by 8); since Deligne settled the commutative case, it is necessarily non-commutative over a non-reduced base.

Graph Theory

Conjectures that every bridgeless graph has a collection of cycles covering each edge exactly twice.

Erdős #793 · Number Theory

Let $F(n)$ be the largest $A\subseteq\{1,\dots,n\}$ with $a\nmid bc$ for distinct $a,b,c\in A$. Is $F(n)=\pi(n)+(C+o(1))\,n^{2/3}(\log n)^{-2}$ for some constant $C$?

Erdős #320 · Number Theory, Unit Fractions

Let $S(N)$ count the distinct values of $\sum_{n\in A} 1/n$ over $A\subseteq\{1,\dots,N\}$. Estimate $S(N)$.

Erdős #321 · Number Theory, Unit Fractions

What is the largest $A\subseteq\{1,\dots,N\}$ such that all subset sums $\sum_{n\in S}1/n$ (over $S\subseteq A$) are distinct?

Erdős #123 · Number Theory

Let $a,b,c>1$ be pairwise coprime integers. Is every large integer a sum of distinct numbers of the form $a^k b^l c^m$ ($k,l,m\ge 0$), none dividing another?

Erdős #119 · Analysis, Polynomials

For unit-modulus complex numbers $z_i$, let $p_n(z)=\prod_{i\le n}(z-z_i)$ and $M_n=\max_{|z|=1}|p_n(z)|$. Erdős's prize question: is there $c>0$ with $\sum_{k\le n} M_k > n^{1+c}$?

Combinatorics, Discrete Geometry

Ziegler proved every simplicial $d$-dimensional 0/1-polytope has at most $2d$ vertices, and asked whether attaining $2d$ vertices forces central symmetry (i.e. a 0/1 cross-polytope). Known true for $d \le 6$; open since ~2000.

Erdős #865 · Number Theory, Additive Combinatorics

Erdős #1197 · Analysis

Erdős #948 · Number Theory, Ramsey Theory

Erdős #986 · Graph Theory, Ramsey Theory

Erdős #619 · Graph Theory

Erdős #696 · Number Theory, Divisors

Erdős #690 · Number Theory

Erdős #750 · Graph Theory, Chromatic Number

Erdős #283 · Number Theory, Unit Fractions

Erdős #351 · Number Theory, Complete Sequences

Erdős #694 · Number Theory

Erdős #90 · Combinatorial Geometry

Conjectured upper bound on how many pairs among $n$ points in the plane can be exactly one unit apart.