Maximizing the number of cliques in $K_{r+1}$-free graphs with forbidden properties

More on Combinatorics & discrete math that day

• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Simple symmetric Venn diagrams with 17 and 19 curves

  We exhibit simple, rotationally symmetric Venn diagrams with 17 curves and with 19 curves: n Jordan curves carried to one another by rotation through 2{\pi}/n, with every one of the 2^n regions present and connected and, since the diagrams are simple, every crossing on exactly two curves.

  Chris Dzoba — arXiv

  PreprintCode available

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures

  We prove the Aldous--Fill conjecture and the Guiduli--Mohar conjecture, as well as the corresponding conjecture for $d$-regular graphs of fixed odd degree.

  Maryam Abdi, Ebrahim Ghorbani — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Lower Bounds for all List-Decodable Deletion Codes

  We prove a lower bound of ${\Omega }_k(2^{n}t{\log }^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$.

  Andrew D. Lin — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

  We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that ${\delta }_{hom}(\{C_3,C_5\},\{C_3\})=\frac{1}{9}$.

  Romain Bourneuf, Raphael Steiner, St\'ephan Thomass\'e and 1 more — arXiv

  Preprint

  Save
• Math & statistics/Combinatorics & discrete mathSep 23, 2026

  Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds

  In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph $G$ of Littlestone dimension $\mathrm{Lit}(G)\le \ell$ has a regular equipartition into excellent sets with $(1+o_{ϵ\to 0,\ell }(1))\cdot {ϵ}^{-\ell -1}$ parts and in the other direction, for every $\ell \in {\mathbb{N}}_{+}$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose equipartitions into good sets must have size at least $(1+o_{ϵ\to 0,\ell }(1))\cdot {ϵ}^{-\ell -1}$.

  Leonardo N. Coregliano, Fernando G. Jeronimo — arXiv

  Preprint

  Save

All new papers on Combinatorics & discrete math