New on arXiv
Sort: by field | by arXiv number | trending
Mathematics
Fourier level inequalities on the discrete cube via complex hypercontractivity and Riesz transforms
Eldan's level-$1{:}3$ inequality is a central tool in his second-order correlation inequalities for increasing Boolean functions. His proof is going to Gaussian space and uses an entropy estimate for second Hermite tensors. We give a direct proof on the discrete hypercube. For increasing real-valued functions $f,g:\{0,1\}^n\to\mathbb R$, we prove $$ W_3[f,g]\ge...
Some polynomial spaces are Euclidean balls
In this paper, we establish a matrix criterion for a space to be homeomorphic to a closed Euclidean ball. As applications, we prove that the normalized space of $K$-Lorentzian polynomials on an arbitrary open convex cone $K$ is homeomorphic to a closed Euclidean ball, giving an affirmative answer to Br\"and\'en and Leake's question, and we also settle Br\"and\'en's conjecture that the normalized...
All minimum cuts of symmetric submodular functions
We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time. The decomposition represents all minimum cuts in linear space. For the pair $s,t$ produced by Queyranne's algorithm, we construct in $O(n^2)$ time a digraph representing exactly the minimum $st$-cuts of the function. Using this construction in Chekuri and Xu's decomposition...
Open Problems on the Null Space and Image Space of the Adjacency Matrix
Akbari, Cameron, and Khosrovshahi proposed two questions concerning the null space and the image space of graphs. Although these problems have been studied in several cases, they have not yet been fully resolved. In this work, we present constructions of graphs that satisfy both the problems.
The probabilistic bound for perfect hashing is sharp only for binary alphabets
We investigate the optimal asymptotic rate $R_q$ of perfect $q$-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science. Let $B_q=-\log_2(1-q!/q^q)/(q-1)$ denote the classical probabilistic lower bound. We prove that $R_q=B_q$ if and only if $q=2$, establishing an explicit strict improvement for every $q\ge3$ and settling the first assertion of a...
On generalized token graphs with tokens of different colors
We generalize the concept of token graphs, and we call them supertoken graphs. In this work, we consider the variant in which tokens are distinguishable (for instance, by color) and at most one token is allowed on each vertex. We formally define this kind of supertoken graphs and present their basic properties. We study their diameter, in which cases they are Cayley graphs, and their spectra....
First-Order Model Checking on Monadically Dependent Graph Classes
Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded twin-width. We show that first-order model checking is fixed-parameter tractable on every monadically dependent graph class. Together with the known hardness result for hereditary classes that are not monadically dependent, this gives...
The Calkin--Wilf problems on $\ell$-ary partition functions
In their 1998 precursor to their celebrated paper ``Recounting the rationals,'' Calkin and Wilf listed nine open problems related to the function $b_{k,\ell}(n)$, the number of partitions of $n$ into powers of $\ell$ with each part appearing at most $k$ times. In this short paper, we answer five of their eight remaining open problems. As a consequence of our results, we extend and generalise...
Idiosynchromatic Poetry
We prove equivalences of asymmetric partition relations involving natural numbers and products of weakly compact cardinals $\kappa$, infinite cardinals $\lambda<\kappa$ and natural numbers to certain classes of finitary problems in the theory of edge-coloured digraphs. We are able to determine three classes of Ramsey numbers exactly, typical examples in these classes are $r(\omega^2 2, 3)$,...
Diameter bounds for complexes that are close to flag or close to normal
The Hirsch problem asks how large the diameter of the dual graph of a simplicial complex can be, in terms of its number of vertices. For normal complexes, the classical bounds are the Larman-Barnette bound, which is linear for fixed dimension, the Kalai-Kleitman bound, which is quasi-polynomial, and the Adiprasito-Benedetti bound n-d, which however holds only for flag complexes. After sharpening...
The universal property of the decomposition space of quasisymmetric functions
Aguiar, Bergeron, and Sottile showed that the coalgebra of quasisymmetric functions is terminal among connected graded coalgebras with a zeta function. After developing the notions of gradings and zeta functions for decomposition spaces, we establish an objective homotopic version of this result. Namely, the decomposition space $Q$ of quasisymmetric functions is terminal: for any conservatively...
On Grassmann $4$-designs
We prove that there is a unique tight $4$-design in the real Grassmannian $G_{2,4}$, up to the action of $O(4)$. Using symmetric association schemes, we also construct an $N$-point $4$-design in $G_{2,4}$ for every even integer $N\geq10$. For symmetric association schemes of order less than $21$, we classify the pairs of rank-three primitive idempotents defining injective maps into $G_{2,4}$;...
Few-Weight Linear Sets and Divisibility of Rank-Metric Codes
We study $\mathbb F_q$-linear sets whose positive point weights belong to a prescribed finite set $A$. The integer $e=\gcd(A)$ always divides the rank of the defining subspace, but the divisibility does not by itself imply linearity over $\mathbb F_{q^e}$. We show that it does in a broad parameter range. Let $L_U$ be an $\mathbb F_q$-linear set of rank $N$ spanning $PG(h-1,q^m)$, $h\ge2$, without...
Domination and maximal intersecting families in comaximal graphs of commutative rings
The comaximal graph $\mathcal{G}(R)$ of a commutative ring $R$ has as vertices the nonunits outside the Jacobson radical, two being adjacent if they generate $R$ as an ideal. For rings with $k\ge 4$ maximal ideals, only the bounds $2\le\gamma(\mathcal{G}(R))\le k$ were known, to our knowledge. We prove $\gamma=\gamma_t=\gamma_c=k$ whenever $3\le k<\infty$, without finiteness or Artinian...
Universal $x$-$y$ duality in equivariant topological recursion and quartic Kontsevich model
Topological recursion is a universal procedure that generates an infinite family of multi-differentials with different interpretations in various areas of mathematics. Recently, a new understanding of topological recursion has emerged from $x$-$y$ duality, which relates two such families through explicit formulae. We study $x$-$y$ duality, its parametrised version, and symplectic duality in the...
Isomorphisms and automorphisms of minimal comaximal hypergraphs of commutative rings
Let $R$ be a commutative ring with exactly $n\ge 2$ maximal ideals and let $k\ge 2$. We study the minimal $k$-uniform comaximal hypergraph $\mathcal{H}_k(R)$, whose vertices are the nonunits outside the Jacobson radical and whose edges are the irredundant $k$-element comaximal families. For $2\le k\le n$ we show that $\mathcal{H}_k(R)$ is a blow-up of the hypergraph of irredundant $k$-coverings...
Clique partitions and distinct color sets in list colorings
For an \(n\)-vertex graph \(G\) and an integer \(m\ge n\), let \(f'(G,m)\) be the minimum number of distinct color sets used by proper colorings from \(m\)-element lists that are disjoint at distinct nonadjacent vertices. A clique-partition assignment gives a common list to the vertices of each part of a clique partition and uses disjoint lists on different parts. In this paper, we construct a...
The parity of the number of missing integers in partitions
Missing integers in partitions have been studied by many authors. A missing integer of a partition is a positive integer smaller than its largest part that does not occur as a part. We investigate parity biases for the number of missing integers in partitions and overpartitions. For every integer $c\ge2$, we prove that the coefficients $a_c(n)$ of $(-cq;q)_\infty/(-q;q)_\infty$ are eventually...
Three-critical hypergraphs of maximum local edge connectivity two
For a hypergraph \(G\), let \(\chi(G)\) denote its chromatic number and \(\lambda(G)\) the maximum, over pairs of distinct vertices, of the minimum size of an edge cut separating the pair. A hypergraph is \(3\)-critical if its chromatic number is three and every proper subhypergraph is two-colorable. In this paper, we give a recursive characterization of the \(3\)-critical hypergraphs with...
A Murnaghan--Nakayama rule for dual stable Grothendieck functions
We give a closed boundary formula for multiplication by power sums in the dual stable Grothendieck basis. The off-diagonal coefficients are signed binomial coefficients supported on corner-connected broken ribbons, which are skew diagrams connected through edges or vertices and containing no square of four boxes. For such a diagram, the smallest power-sum index with a nonzero coefficient is the...
On the classification of $2$-distance-primitive graphs of small valency
A non-complete vertex-transitive graph is called 2-distance-primitive if a vertex stabilizer acts primitively on both the first and second distance neighborhoods of the vertex. Recently, Ruan, Liu and Jin [Discrete Math. 347 (2024), 113978] showed that every connected 2-distance-primitive graph of valency at most 9 either belongs to certain known families or satisfies a collection of further...
Anti-ribbon shaped Young diagram decomposition
We introduce a sliding procedure on diagrams which splits the standard Young tableaux of a corner-crossed diagram, in particular of a skew shape, along a finite binary tree whose leaves are anti-ribbon diagrams. Combined with standardization, this yields a decomposition of semi-standard Young tableaux into tableaux of anti-ribbon shape, indexed by standard tableaux and governed by their descent...
Web bases for the Lie superalgebra $\mathfrak{gl}(1|1)$
Queffelec--Sartori and Tubbenhauer--Vaz--Wedrich give a diagrammatic web category via generators and relations to describe the subcategory of Rep($\mathfrak{gl}(m|n)$) generated by tensor products of exterior powers of the defining representation. We construct the first explicit bases for homomorphism spaces in the web category for $\mathfrak{gl}(1|1)$, giving an alternative diagrammatic...
A Universal Threshold Theory for Local Properties of Random Linear Codes
Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes. A monotone property is $b$-local if a collection of at most $b$ codewords can witness its satisfaction or failure, as in list decoding and list recovery. The threshold of $\mathcal P$ is the code dimension at which the probability that an...
Combinatorics of noncommutative harmonic oscillator determinant
We obtain an explicit evaluation of the determinants that appear in the denominators of the integrands for the iterated integrals expressing special values of the spectral zeta function of the noncommutative harmonic oscillator at integers greater than 1. The determinants in question are those of cyclic tridiagonal matrices; their explicit evaluation is carried out, in addition to the...
Probability model of connectedness for graphs with logarithmical degree
For a graph $G$ of order $N$, an integer $k$ with $0\leq k< N$ and a real number $p$ with $0\leq p\leq 1$, let $p(G,k)$ and $t(G,p)$ be the probabilities that $G$ is disconnected when $k$ vertices are removed randomly and when each vertex is removed independently with probability $p$, respectively. We deduce a formula of $p(G,k)$ for Harary graphs and show that the phase transition on $p(G,k)$...
Generalized Chromatic Polynomials of Cycles and uni-cyclic Graphs
In \cite{R81}, Read obtained an explicit formula for the generalized chromatic polynomials of cycle graphs using the classical deletion-contraction principle. In this paper, we take a linear-algebraic approach and present a new proof of Read's formula by realizing the generalized chromatic polynomials of cycle graphs as traces of certain linear operators. As an application of this approach, we...
Structure of adjacency algebras of thin Jordan schemes
We prove that adjacency algebras of Jordan schemes over fields of characteristic zero are semisimple. We then classify the adjacency algebras of thin Jordan schemes over the fields of real numbers or complex numbers. The simple summands of the adjacency algebras over these fields are restricted to specific types of simple Jordan algebras.
Strict unimodality without log-concavity for partial Petrial polynomials
For a simple graph $G$, the partial Petrial polynomial $P_G^{\times}(z)$ enumerates all diagonal perturbations of its adjacency matrix over $GF(2)$ by rank. We derive a rooted attachment identity and apply it to the tree $R_m$ obtained by joining a new vertex to the middle vertex of each of $m$ disjoint copies of the five-vertex path. We prove that the nonzero coefficient sequence of...
Distinguishing invariants of Cayley Graphs, Hamming graphs, and wreath product actions
Let $\Gamma$ be a nontrivial group that acts on a graph $G=(V,E)$. The total distinguishing number $D''_{\Gamma}(V\cup E)$ (distinguishing index $D'_{\Gamma}(E)$) of the action is the least number of labels required for a total labeling (edge labeling) of $G$ so that the only elements of $\Gamma$ that preserve the labeling belong to the pointwise stabilizer of $V\cup E$ (pointwise stabilizer of...
Decomposable polytopes with few vertices
A polytope $P$ is decomposable if it can be written as the Minkowski sum of two polytopes that are not homothetic to it. It is well known that decomposable $d$-dimensional polytopes with $2d$ or fewer vertices are the simplicial prisms. More recent work shows that, with two exceptions in low dimensions, decomposable $d$-dimensional polytopes with exactly $2d+1$ vertices are either pentasms or...
Connected graphs having maximum signless Laplacian spectral radius
Let $\rho(G)$ denote the signless Laplacian spectral radius of a graph $G$, and let $\mathcal C_{n,m}$ be the family of connected graphs of order $n$ and size $m$. A graph is $Q$-maximal if it maximizes $\rho(G)$ over this family. Motivated by a question of Chang and Tam (2011), we study this extremal problem using scalar identities and coronal methods for threshold graphs. From the Perron...
Prescribed Color Patterns in Tight Hamilton Cycles and Spanning Trees
We compare transversal and pattern thresholds for two spanning structures. For every fixed $k\ge 3$ and $\alpha>0$, we prove that every sufficiently large $n$-vertex $k$-graph collection with minimum codegree at least $(1/2+\alpha)n$ contains a tight Hamilton cycle with any prescribed color pattern. Hence the transversal and pattern thresholds for tight Hamilton cycles coincide asymptotically....
The Higman-Sims graph and a geometric construction of the Steiner system $S(3,6,22)$
The Higman-Sims graph is the unique strongly regular graph with parameters $(100,22,0,6)$. In this paper, we show that the only distance-regular antipodal double cover of the Higman-Sims graph is its bipartite double cover. Our main tool is a geometric construction of the Steiner system $S(3,6,22)$.
The $q$-Poincar\'e sum and separability in a Coxeter group
Given a finite Coxeter group $W$ and an element $q$ of a commutative ring $\mathbf{k}$, we define the element $\mathbf{L}_{q} :=\sum_{w\in W}q^{\ell\left( w\right) }w$ of its group algebra $\mathbf{k}\left[ W\right] $. We say that an element $w\in W$ is $W$\emph{-length-symmetric} if its coefficient in the commutator $\left[ \mathbf{L}_{a},\mathbf{L}_{b}\right] $ is $0$ for all $\mathbf{k}$ and...
Two-row Schur times Schubert via parallel classes of positroid varieties
Schubert structure constants are intersection numbers of Schubert varieties. Finding positive combinatorial formulas for these constants remains a major open problem. We resolve this problem when one of the indexing permutations corresponds to a two-row partition. Our approach uses increasing chains, introduced by Sottile for the one-row case, and builds on the skew Schubert functions studied by...
On the number of edges in quasiplanar graphs
A $k$-quasiplanar graph is a graph drawn in the plane with no $k$ pairwise crossing edges. Pach, Shahrokhi, and Szegedy conjectured that every such graph on $n$ vertices has $O_k(n)$ edges. ChatGPT produced a proof of this conjecture. Here, we present a simplified, self-contained version of that proof.
Gaps in the Most Frequent Sizes of Integer Sumsets
Nathanson observed that, for four-element sets $A$ of integers, the most frequent sizes of the iterated sumset $hA$ are separated by triangular numbers. Senger proved this and suggested an analogue for larger sets. We establish this pattern for $k$-element subsets of $\{1,\ldots,q\}$, for every fixed $k\geq3$, where $h\geq2$ is either fixed or grows slower than $q^{1/(2k-1)}$. As $q\to\infty$,...
Ultrahomogeneous hypertournaments
A $k$-hypertournament is a higher-arity generalisation of a tournament, consisting of a set together with an irreflexive $k$-ary relation such that the automorphism group of each substructure of size $k$ is the alternating group $\mathrm{A}_k$. We show that, for each $k \geq 3$, there are continuum-many non-isomorphic countable ultrahomogeneous $k$-hypertournaments, answering a question of...
Rational Tur\'an exponents of a single $k$-uniform hypergraph
For a fixed $k$-uniform hypergraph $F$, let $\mathrm{ex}_k(n,F)$ denote the maximum number of edges in an $F$-free $k$-uniform hypergraph on $n$ vertices. We prove that for every integer $k\ge2$ and every rational $r\in[0,1]$ there exists a $k$-uniform hypergraph $F_{k,r}$ such that \begin{equation*} \mathrm{ex}_k(n,F_{k,r})=\Theta(n^{k-r}). \end{equation*} The case $k=2$ is the rational...
Pattern avoidance classes of parking permutations with fixed lucky sets
For a parking function, the resulting sequence after all cars have parked is called the associated parking permutation. For each parking function, cars that park in their preferred spot are called lucky cars. In this paper, we enumerate parking permutations that avoid a specified set of permutation patterns in $\mathfrak{S}_3$ and whose lucky cars are the first $k$ cars. Often, the enumeration...
$s$-quasi-transitive weakly distance-regular digraphs
A digraph is $s$-quasi-transitive if, for every path $(x_0,x_1,\ldots,x_s)$ of length $s$, either $(x_0,x_s)\in A\Gamma$ or $(x_s,x_0)\in A\Gamma$ (or both). In this paper, we give a characterization of $s$-quasi-transitive commutative weakly distance-regular digraphs, where $s=4$, or $s\geq 5$ and the cycle polar diameter is at least $s$.
Exact penalties for maximum-edge bicliques in bipartite graphs
Given a bipartite graph $G$, we denote by $g(G)$ the largest product $|A||B|$ over pairs of vertex sets $A$ and $B$, one on each side, with no edge between them. These pairs are the bicliques of the bipartite complement of $G$; hence, computing $g(G)$ is the maximum-edge biclique problem, which is NP-hard, as shown by Peeters in 2003. Gillis and Glineur characterized it by a continuous quadratic...
On Packed Passenger Permutations
An occupied seat in a binary row is called packed if both of its immediate neighbors are occupied. We give a self-contained combinatorial account of this statistic, equivalently the number of overlapping occurrences of 111. An occupied-block decomposition yields a coefficient formula at fixed occupancy and a direct proof of the sharp minimum max{0,3m-2n-2} for m passengers in n seats, including...
An improved bound for the intersection of two longest cycles in $k$-connected graphs
A conjecture attributed to Smith states that in every $k$-connected graph, every pair of longest cycles intersects in at least $k$ vertices. We prove that every two longest cycles in a $k$-connected graph on $n$ vertices intersect in at least $\min\{k,10k-n-30\}$ vertices. Consequently, Smith's conjecture holds whenever $k\ge \frac{n+30}{9}$. This improves the previous bound of $\frac{n+16}{7}$...
An extremal unimodular lattice of rank 37
We construct an extremal unimodular lattice of rank 37, resolving the last undetermined optimal minimum in ranks at most 48. The construction begins with the Cayley table of $\mathbb{Z}/13\mathbb{Z}$, assigning a vector of norm four to each cell. We prove that the resulting incidence lattice has exactly 26 unimodular completions of minimum four, all isometric. The resulting Cayley lattice...
Perfect Partitions of Regular Bipartite Graphs
Let $I_{n,n}$ be a fixed perfect matching of the complete bipartite graph $K_{n,n}$, and let $L_{n,1}=K_{n,n}-I_{n,n}$. A perfect set of $L_{n,1}$ is a $1$-factorization of $L_{n,1}$, that is, a set of $n-1$ pairwise edge-disjoint perfect matchings whose union is $E(L_{n,1})$; a perfect partition of $L_{n,1}$ is a partition of the set of all perfect matchings of $L_{n,1}$ into perfect sets....
An improved lower bound for maximal partial Room squares
We establish a new asymptotic lower bound for the volume of a maximal partial Room square of even order $n$. We prove that its volume is at least $\frac{2\sqrt{66}-6}{57}n^2-O(n)$, improving the leading coefficient $1/8$ in the lower bound obtained by Meszka and Rosa. The proof combines two counting arguments, one based on a transversal of empty cells and the other on the graph of occurring...
Seeking the dense half in $K_4$-free graphs
We show that every $K_4$-free graph on $n$ vertices has a balanced bipartition such that neither part contains more than $0.0671n^2 + o(n^2)$ edges. This improves the previous best bound of $0.074n^2$ by Xu and Zhang. We also formulate a conjecture that the tight bound for this problem is $\frac{425}{6498}n^2 \approx 0.0654n^2$, and present a construction showing that it would be best possible.
Resolving Tusn\'ady's Problem
We prove a lower bound of $\Omega_d((\log N)^{d-1/2})$ for the worst-case combinatorial discrepancy of $N$-point sets with respect to anchored boxes in every fixed dimension $d\ge3$. Together with Nikolov's upper bound of the same order and Wei's planar lower bound, this settles Tusn\'ady's problem: the discrepancy of axis-parallel boxes is $\Theta_d((\log N)^{d-1/2})$ in every fixed dimension...
Only titles, authors and the start of each abstract are shown here, as arXiv published them. Open a paper to read its whole abstract and, with your own AI key, a plain-language summary. Papers on arXiv are preprints and may not have been peer reviewed.
Data from arXiv, used through the arXiv API. Thank you to arXiv for use of its open access interoperability.