Skip to content

Problems · Vela Mathematics Program

Narrowed tograph theory ×source:vibemathed ×Clear all

Problem ledger

13 problemsGraph view
declared open · formalizederdos:130
For an infinite planar set in strong general position, how large can the chromatic and clique numbers of its positive-integer-distance graph be - in particular, can the chromatic number be infinite? Yes: there is such a set, no three collinear and no four concyclic, with infinite chromatic number.
graph theorychromatic numberN/A4 sources
declared open (Lean) · formalized · $500erdos:146
If HH is bipartite and rr-degenerate, is ex(n;H)≪n2−1/r\mathrm{ex}(n;H) \ll n^{2-1/r} (a $500 Erdős-Simonovits prize conjecture)? A counterexample refutes the degeneracy conjecture.
graph theoryturan numberN/A3 sources
declared open (Lean) · formalizederdos:180
For every finite family F\mathcal{F} of graphs, is there a single G∈FG \in \mathcal{F} with ex(n;G)≪Fex(n;F)\mathrm{ex}(n;G) \ll_{\mathcal{F}} \mathrm{ex}(n;\mathcal{F})? A counterexample refutes the Erdős-Simonovits compactness conjecture.
graph theoryturan numberN/A4 sources
declared open (Lean) · formalized · $250erdos:183
Let R(3;k)R(3;k) be the least nn such that every kk-colouring of the edges of KnK_n contains a monochromatic triangle. Determine lim⁡k→∞R(3;k)1/k\lim_{k\to\infty} R(3;k)^{1/k} (a $250 Erdős prize problem). A superexponential lower bound resolves the problem: the limit is infinite.
graph theoryramsey theoryA0033233 sources
declared openerdos:550
Let m1≤⋯≤mkm_1\leq\cdots\leq m_k and nn be sufficiently large. If TT is a tree on nn vertices and GG is the complete multipartite graph with vertex class sizes m1,…,mkm_1,\ldots,m_k, prove that R(T,G)≤(χ(G)−1)(R(T,Km1,m2)−1)+m1R(T,G)\leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1.
graph theoryramsey theoryN/A4 sources
declared openerdos:584
Must every graph with nn vertices and δn2\delta n^2 edges contain large subgraphs in which every two edges lie on specified short cycles? A dense high-girth construction refutes the statement when δ\delta may shrink with nn.
graph theorycyclesN/A2 sources
declared open · formalized · $500erdos:593
Erdos Problem #593 asks which finite triple systems occur in every uncountably chromatic triple system. The answer is exactly the class generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and one-point amalgamations. Problem #1177 on exact spectra is settled alongside it.
set theorygraph theoryhypergraphsN/A4 sources
declared proved (Lean)erdos:610
Erdős problem 610
graph theorypossible4 sources
declared solved (Lean) · formalizederdos:619
False ↔ ∃ c > 0, ∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V), G.Connected → G.CliqueFree 3 → ↑(Erdos619.minNewEdges 4 G) < (1 - c) * ↑(Fintype.card V)
graph theoryN/A5 sources
declared proved (Lean) · formalizederdos:750
True ↔ ∀ (f : ℕ → NNReal), Filter.Tendsto f Filter.atTop Filter.atTop → ∃ V G, G.chromaticNumber = ⊤ ∧ ∀ (m : ℕ) (S : Set V), 0 < m → S.ncard = m → ∃ I ⊆ S, G.IsIndepSet I ∧ ↑m / 2 - f m ≤ ↑I.ncard
graph theorychromatic numberN/A5 sources
declared provederdos:986
Erdős problem 986
graph theoryramsey theoryA000791 · A0594423 sources
declared proved (Lean) · formalizederdos:1014
∀ (k : ℕ), 3 ≤ k → Filter.Tendsto (fun l => ↑R(k, l + 1) / ↑R(k, l)) Filter.atTop (nhds 1)
graph theorypossible7 sources
declared openerdos:1032
Do arbitrarily large 4-chromatic edge-critical graphs exist with minimum degree bounded below by a positive constant times the number of vertices?
graph theorychromatic numberpossible3 sources