299 papers
This paper confirms two conjectures by establishing that the sum of the sizes of the union and intersection of all maximum independent sets is bounded by $2\alpha(G)2\alpha(G)$, thereby unifying these results into a comprehensive chain of inequalities involving core, corona, nucleus, and diadem sets.
This paper proves that the conjecture stating every minimal --factor critical graph satisfies holds true for the class of -planar graphs, thereby resolving the conjecture specifically for planar graphs.
This paper investigates the selection of optimal two-block partitions to accelerate Markov chain mixing by establishing theoretical connections between KL divergence and Frobenius distance objectives and their respective decay rates, while proposing computationally feasible approximation algorithms to solve the resulting combinatorial optimization problem.
This paper establishes that for a set of points in the plane with diameter at most 1, the ratio of pairs with distance to pairs with distance is bounded below by , thereby improving upon Steinerberger's previous bound and nearly confirming the conjectured asymptotic behavior.
This paper confirms two conjectures by Huang, Huang, and Cioabă by proving that the full-flag Johnson graph exhibits an Aldous-type spectral-gap phenomenon, specifically demonstrating that its spectral gap equals that of its Schreier quotient derived from the point-stabiliser equitable partition.
This paper provides the first complete proof of a closed formula involving Beatty-type bracket expressions for determining P-positions in additive subtraction games within the primitive quadratic regime, while also establishing that the full nim-value structure resides on linear shifts of these classical P-positions.
This paper establishes a new lower bound of 11948 for the kissing number in 19 dimensions by combining Cohn and Li's odd-sign construction with an explicit nonlinear binary code of length 19 derived from nested codes within a punctured extended binary Golay code.
This paper establishes the existence, uniqueness, and exponential convergence of a Ricci flow with prescribed curvature on finite graphs, proving that constant curvature weights exist under specific density conditions and thereby providing an affirmative answer to Chow and Luo's Question 2 regarding combinatorial Ricci flows.
This paper establishes asymptotic bounds for the Ramsey number , which guarantees a monochromatic subgraph with Hadwiger number in any -edge-coloring of a complete graph, showing that this value grows proportionally to .
This paper develops explicit and compact formulas for the M-polynomial of seven specific graph products, providing a unified framework to analyze how vertex-degree interactions propagate under these constructions and extending existing results for degree-based topological indices.
This paper employs graph transformation methods to determine the maximum inverse sum indeg (ISI) indices and characterize the corresponding extremal trees and unicyclic graphs with a fixed diameter.
This paper investigates anti-Ramsey numbers for weak and strong copies of posets within the power set $2^{[n]}$, establishing their connections to extremal numbers and determining asymptotic results for tree and crown posets.
This paper establishes the first central limit theorems for the number of edges and unimodular triangulation edges in symmetric edge polytopes generated by Erdős–Rényi random graphs in high dimensions, utilizing the discrete Malliavin–Stein method to derive precise asymptotics and identify an atypical fluctuation regime where variance cancellation occurs.
This paper presents a polynomial-size representation and a corresponding polynomial-time construction algorithm for the family of all sets with a fixed value in integer-valued symmetric submodular functions, thereby generalizing low-rank structure theorems from graph cut-rank functions to broader connectivity functions and enabling efficient solutions to cardinality-constrained minimization problems.
This paper proves that the leading and penultimate leading coefficients of the error terms for the NRS(2) method applied to a cubic polynomial are positive-coefficient polynomials in the variables and , thereby simplifying and extending previous results.
This paper establishes that factors of smooth words are f-smooth and advances Sing's conjecture on their complexity by proving the asymptotic growth rate for even alphabets, confirming the lower bound for all binary alphabets, and improving the upper bound for odd alphabets.
This paper introduces the concepts of vertex dismissible and scalable simplicial complexes as generalizations of vertex decomposability and shellability, establishing their algebraic characterizations via Alexander duality, proving their equivalence to weak connectedness for specific graph classes, and providing a unified skeletal framework that recovers numerous classical theorems.
This paper proves that for sufficiently large , the uniform probability measures on three specific families of spanning subgraphs of the complete graph —namely connected spanning subgraphs, forests with exactly components, and connected spanning subgraphs with excess —satisfy the pairwise negative correlation property.
This paper establishes a novel connection between digraph extremal problems and uniform Turán densities of 3-graphs to provide verifiable conditions for determining specific density values, including identifying new classes of 3-graphs with densities such as , , and $4/271/27$.
This paper presents new combinatorial perspectives on partitions with distinct even parts by connecting them to signed and bicolored partitions to derive several identities and provide bijective proofs that partially resolve open problems posed by Andrews-El Bachraoui and Kılıç-Kurşungöz.