The degeneracy and Alon-Tarsi number under -sum operations
This paper characterizes graphs with an Alon-Tarsi number of 2 and investigates the relationship between the Alon-Tarsi number and degeneracy under -sum operations.
🔢 Category
math.CO
299 papers
Models of random spanning trees
This paper develops quantitative tools to study random minimum spanning trees (MST) generated by assigning independent edge weights from arbitrary distributions, addressing the gap in mathematical understanding between these practical algorithms and the more extensively studied uniform spanning trees.
Extremal -intersecting families for finite sets with -covering number at least
This paper characterizes the maximum size and structure of -intersecting families of -subsets from an -element set with a -covering number of at least for sufficiently large , generalizing two previous results by Frankl.
Multigraded Betti numbers of Veronese embeddings
This paper investigates the multigraded Betti numbers of Veronese embeddings by interpreting them through Hochster's formula as homology groups of specific simplicial complexes and utilizing Forman's discrete Morse theory to establish vanishing and non-vanishing results.
On the quantum chromatic number of Hamming and generalized Hadamard graphs
This paper establishes an exponential separation between the quantum and classical chromatic numbers for -ary Hamming and generalized Hadamard graphs by determining exact quantum values through new linear programming and trace method techniques, while deriving classical lower bounds via the forbidden intersection pattern method.
Extremal Bounds on the Sigma and Albertson Indices for Non-Decreasing Degree Sequences
This paper establishes sharp extremal bounds for the Albertson and Sigma irregularity indices of trees with prescribed degree sequences, demonstrating that caterpillar trees serve as key extremal configurations and highlighting the quadratic growth of the Sigma index relative to the linear Albertson index.
Linear colorings of graphs
This paper investigates the properties of the linear chromatic number, a parameter introduced to relax treedepth, and establishes improved bounds for this relationship across various graph classes, addressing a conjecture by Kun et al. regarding the upper bound of treedepth in terms of linear chromatic number.
Murnaghan-Nakayama rule for the cyclotomic Hecke algebra and applications
This paper establishes a Murnaghan-Nakayama rule for the irreducible characters of the cyclotomic Hecke algebra on Shoji's standard elements, providing a direct combinatorial method to compute full character tables, deriving dual iterative formulas, and applying these results to obtain new character sum formulas and orthogonality relations.
Engel and co-Engel graphs of finite groups
This paper investigates the structural and spectral properties of Engel and co-Engel graphs associated with finite groups, establishing that the undirected Engel graph does not uniquely determine its directed counterpart, characterizing isolated vertices via the Fitting subgroup, and computing topological and spectral invariants to classify non-Engel groups with specific graph-theoretic constraints.
On the size and complexity of scrambles
This paper introduces the carton number to demonstrate that scramble number is not an NP certificate due to exponential certificate size, while also characterizing graph families with polynomial-time approximations, establishing fixed-parameter tractability for disjoint scramble number, and deriving new bounds on scramble number via vertex congestion.
Digraph Branchings and Matrix Determinants
This paper presents an extended version of the matrix-tree theorem that accommodates non-zero column sums by introducing a root vertex, thereby enabling the proof of an all-minors theorem and its application to discrete time-evolution systems and determinant computation strategies.
The graph minor relation satisfies the twin alternative conjecture
This paper proves that the graph minor relation satisfies the Tree Alternative Conjecture, demonstrating that the equivalence class of any tree under this relation is either trivial or infinite.
On distribution of the depth index on perfect matchings
This paper investigates the depth index statistic on perfect matchings by providing a new combinatorial description and calculating its generating polynomial, ultimately proving that this statistic is equidistributed with the rank function of the Bruhat order.
The complexity of finite smooth words over binary alphabets
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.
Large chirotopes with computable numbers of triangulations
This paper generalizes decomposition methods for chirotopes to develop a precise asymptotic estimate for the number of triangulations of the double circle by applying functional equations and the kernel method.
An asymptotically optimal bound for the concentration function of a sum of independent integer random variables
This paper proves an asymptotically optimal bound for the concentration function of a sum of independent integer random variables, confirming that the sum's maximum point probability is bounded by that of a corresponding sum of minimal-variance variables when the total variance is sufficiently large, thereby extending the result to separable Hilbert spaces.
Schur complements for tensors and multilinear commutative rank
This paper establishes the equivalence of three notions of rank for matrices of multilinear forms, thereby generalizing Flanders' classical result, correcting prior work by Fortin and Reutenauer, resolving a question posed by Lampert, and proving a special case of the conjecture linking analytic and partition ranks of tensors.
Extremal Laplacian energy of -free digraphs
This paper extends Turán problems to the spectral domain of digraphs by determining the maximum Laplacian energy and characterizing the extremal digraphs for the class of -free digraphs.
Semidegree threshold for spanning trees in oriented graphs
The paper proves that for any fixed maximum degree and any , every sufficiently large oriented graph with minimum semidegree at least contains every oriented tree on vertices with maximum degree at most , a bound that is asymptotically optimal.
New Upper Bounds for the Classical Ramsey Numbers , and
This paper establishes new, improved upper bounds for the classical Ramsey numbers , , and , surpassing the previous limits derived from the standard recursive inequality.