------------------------------------------------------------------------------
------------------------------------------------------------------------------
Send any comments regarding submissions directly to submitter.
------------------------------------------------------------------------------
Archives at http://arxiv.org/archive/math
To unsubscribe, e-mail To: math@arxiv.org, Subject: cancel
------------------------------------------------------------------------------
Submissions to:
Combinatorics
received from Thu 10 Jul 25 18:00:00 GMT to Fri 11 Jul 25 18:00:00 GMT
------------------------------------------------------------------------------
------------------------------------------------------------------------------
\\
arXiv:2507.08083
Date: Thu, 10 Jul 2025 18:00:04 GMT (20kb)
Title: Symmetric quasisymmetric Schur-like functions
Authors: Maria Esipova, Jinting Liang, Stephanie van Willigenburg
Categories: math.CO
Comments: 24 pages
\\
In this paper we classify when (row-strict) dual immaculate functions and
(row-strict) extended Schur functions, as well as their skew generalizations,
are symmetric. We also classify when their natural variants, termed advanced
functions, are symmetric. In every case our classification recovers classical
skew Schur functions.
\\ ( https://arxiv.org/abs/2507.08083 , 20kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08139
Date: Thu, 10 Jul 2025 19:56:34 GMT (24kb)
Title: Finding a solution to the Erd\H{o}s-Ginzburg-Ziv theorem in
$O(n\log\log\log n)$ time
Authors: Yui Hin Arvin Leung
Categories: math.CO cs.DS
Comments: 22 pages, 0 figures
\\
The Erd\H{o}s-Ginzburg-Ziv theorem states that for any sequence of $2n-1$
integers, there exists a subsequence of $n$ elements whose sum is divisible by
$n$. In this article, we provide a simple, practical $O(n\log\log n)$ algorithm
and a theoretical $O(n\log\log\log n)$ algorithm, both of which improve upon
the best previously known $O(n\log n)$ approach. This shows that a specific
variant of boolean convolution can be implemented in time faster than the usual
$O(n\log n)$ expected from FFT-based methods.
\\ ( https://arxiv.org/abs/2507.08139 , 24kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08247
Date: Fri, 11 Jul 2025 01:21:07 GMT (36302kb,A)
Title: On 3-terminal positions in Hex
Authors: Eric Demer and Peter Selinger
Categories: math.CO
Comments: 43 pages
MSC-class: 91A46
\\
This paper is about 3-terminal regions in Hex. A 3-terminal region is a
region of the Hex board that is completely surrounded by black and white
stones, in such a way that the black boundary stones form 3 connected
components. We characterize Hex as the universal planar Shannon game of degree
3. This ensures that every Hex position can be decomposed into 3-terminal
regions. We then investigate the combinatorial game theory of 3-terminal
regions. We show that there are infinitely many distinct Hex-realizable values
for such regions. We introduce an infinite family of 3-terminal positions
called superswitches and investigate their properties. We also present a
database of Hex-realizable 3-terminal values, and illustrate its utility as a
problem-solving tool by giving various applications. The applications include
the automated verification of connects-both templates and pivoting templates, a
new handicap strategy for $11\times 11$ Hex, and a method for constructing
witnesses for the non-inferiority of probes in many Hex templates. These
methods allow us to disprove a conjecture by Henderson and Hayward.
\\ ( https://arxiv.org/abs/2507.08247 , 36302kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08324
Date: Fri, 11 Jul 2025 05:27:14 GMT (57kb)
Title: Degree conditions for spanning expansion hypertrees
Authors: Mengjiao Rao, Nicol\'as Sanhueza-Matamala, Lin Sun, Guanghui Wang,
Wenling Zhou
Categories: math.CO
\\
The $k$-expansion of a graph $G$ is the $k$-uniform hypergraph obtained from
$G$ by adding $k-2$ new vertices to every edge. We determine, for all $k > d
\geq 1$, asymptotically optimal $d$-degree conditions that ensure the existence
of all spanning $k$-expansions of bounded-degree trees, in terms of the
corresponding conditions for loose Hamilton cycles. This refutes a conjecture
by Pehova and Petrova, who conjectured that a lower threshold should have
sufficed. The reason why the answer is off from the conjectured value is an
unexpected `parity obstruction': all spanning $k$-expansions of trees with only
odd degree vertices require larger degree conditions to embed. We also show
that if the tree has at least one even-degree vertex, the codegree conditions
for embedding its $k$-expansion become substantially smaller.
\\ ( https://arxiv.org/abs/2507.08324 , 57kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08483
Date: Fri, 11 Jul 2025 10:54:15 GMT (15kb)
Title: Word-Representability of Split Graphs with Independent Set of Size 4
Authors: Suchanda Roy and Ramesh Hariharasubramanian
Categories: math.CO cs.DM
\\
A pair of letters $x$ and $y$ are said to alternate in a word $w$ if, after
removing all letters except for the copies of $x$ and $y$ from $w$, the
resulting word is of the form $xyxy\ldots$ (of even or odd length) or
$yxyx\ldots$ (of even or odd length). A graph $G = (V (G), E(G))$ is
word-representable if there exists a word $w$ over the alphabet $V(G)$, such
that any two distinct vertices $x, y \in V (G)$ are adjacent in $G$ (i.e., $xy
\in E(G)$) if and only if the letters $x$ and $y$ alternate in $w$. A split
graph is a graph in which the vertices can be partitioned into a clique and an
independent set. Word-representability of split graphs has been studied in a
series of papers [2, 5, 7, 9] in the literature. In this work, we give a
minimal forbidden induced subgraph characterization of word-representable split
graphs with an independent set of size 4, which is an open problem posed by
Kitaev and Pyatkin in [9]
\\ ( https://arxiv.org/abs/2507.08483 , 15kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08353
Date: Fri, 11 Jul 2025 07:06:21 GMT (10kb)
Title: The Induced Saturation Number for $\mathcal{V}_3$ is Linear
Authors: James Brownlie, Sean Jaffe
Categories: math.CO
Comments: 8 pages, 7 figures
MSC-class: 06A07, 05D05
\\
Given a poset $\mathcal{P}$, a family $\mathcal{F}$ of elements in the
Boolean lattice is said to be $\mathcal{P}$-saturated if $\mathcal{F}$ does not
contain an induced copy $\mathcal P$, but every proper superset of
$\mathcal{F}$ contains one. The minimum size of a $\mathcal P$-saturated family
in the $n$-dimensional Boolean lattice is denoted by $sat^*(n,\mathcal{P})$. In
this paper, we consider the poset $\mathcal V_3$ (the four element poset with
one minimal element and three incomparable maximal elements) and show that
$sat^*(n,\mathcal{V}_3)\geq \frac{n}{2}$. This represents the first linear
lower bound for $sat^*(n,\mathcal{V}_3)$, improving upon the previously
best-known bound of $2\sqrt{n}$. Our result establishes that
$sat^*(n,\mathcal{V}_3) = \Theta(n)$.
\\ ( https://arxiv.org/abs/2507.08353 , 10kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08433
Date: Fri, 11 Jul 2025 09:19:58 GMT (31kb)
Title: On the $(k,\ell)$-multiset anonymity measure for social graphs
Authors: Alejandro Estrada-Moreno, Elena Fern\'andez, Dorota Kuziak, Manuel
Mu\~noz-M\'arquez, Rolando Trujillo-Rasua, Ismael G. Yero
Categories: math.CO cs.IT math.IT
Comments: 25 pages
\\
The publication of social graphs must be preceded by a rigorous analysis of
privacy threats against social graph users. When the threat comes from inside
the social network itself, the threat is called an active attack, and the
de-facto privacy measure used to quantify the resistance to such an attack is
the $(k,\ell)$-anonymity. The original formulation of $(k,\ell)$-anonymity
represents the adversary's knowledge as a vector of distances to the set of
attacker nodes. In this article, we argue that such adversary is too strong
when it comes to counteracting active attacks. We, instead, propose a new
formulation where the adversary's knowledge is the multiset of distances to the
set of attacker nodes. The goal of this article is to study the
$(k,\ell)$-multiset anonymity from a graph theoretical point of view, while
establishing its relationship to $(k,\ell)$-anonymity in one hand, and
considering the $k$-multiset antiresolving sets as its theoretical frame, in a
second one. That is, we prove properties of some graph families in relation to
whether they contain a set of attacker nodes that breaks the
$(k,\ell)$-multiset anonymity. From a practical point of view, we develop a
linear programming formulation of the $k$-multiset antiresolving sets that
allows us to calculate the resistance of social graphs against active attacks.
This is useful for analysts who wish to know the level of privacy offered by a
graph.
\\ ( https://arxiv.org/abs/2507.08433 , 31kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08114
Date: Thu, 10 Jul 2025 18:55:02 GMT (11kb)
Title: Exact Biclique Partition number of Split Graphs
Authors: Anand Babu, Ashwin Jacob
Categories: math.CO cs.DM
\\
The biclique partition number of a graph \(G\), denoted \(
\operatorname{bp}(G)\), is the minimum number of biclique subgraphs that
partition the edge set of \(G\). The Graham-Pollak theorem states that the
complete graph on \( n \) vertices cannot be partitioned into fewer than \( n-1
\) bicliques. In this note, we show that for any split graph \( G \), the
biclique partition number satisfies \( \operatorname{bp}(G) =
\operatorname{mc}(G^c) - 1 \), where \( \operatorname{mc}(G^c) \) denotes the
number of maximal cliques in the complement of \( G \). This extends the
celebrated Graham-Pollak theorem to a broader class of graphs.
\\ ( https://arxiv.org/abs/2507.08114 , 11kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08503
Date: Fri, 11 Jul 2025 11:24:46 GMT (23kb)
Title: Bounds on the game isolation number and exact values for paths and
cycles
Authors: Csilla Bujt\'as and Tanja Dravec and Michael A. Henning and Sandi
Klav\v{z}ar
Categories: math.CO
\\
The isolation game is played on a graph $G$ by two players who take turns
playing a vertex such that if $X$ is the set of already played vertices, then a
vertex can be selected only if it dominates a vertex from a nontrivial
component of $G \setminus N_G[X]$, where $N_G[X]$ is the set of vertices in $X$
or adjacent to a vertex in $X$. Dominator wishes to finish the game with the
minimum number of played vertices, while Staller has the opposite goal. The
game isolation number $\iota_{\rm g}(G)$ is the number of moves in the
Dominator-start game where both players play optimally. If Staller starts the
game the invariant is denoted by $\iota_{\rm g}'(G)$. In this paper,
$\iota_{\rm g}(C_n)$, $\iota_{\rm g}(P_n)$, $\iota_{\rm g}'(C_n)$, and
$\iota_{\rm g}'(P_n)$ are determined for all $n$. It is proved that there are
only two graphs that attain equality in the upper bound $\iota_{\rm g}(G) \le
\frac{1}{2}|V(G)|$, and that there are precisely eleven graphs which attain
equality in the upper bound $\iota_{\rm g}'(G) \le \frac{1}{2}|V(G)|$. For
trees $T$ of order at least three it is proved that $\iota_{\rm g}(T) \le
\frac{5}{11}|V(T)|$. A new infinite family of graphs $G$ is also constructed
for which $\iota_{\rm g}(G) = \iota_{\rm g}'(G) = \frac{3}{7}|V(G)|$ holds.
\\ ( https://arxiv.org/abs/2507.08503 , 23kb)
%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-
------------------------------------------------------------------------------
\\
arXiv:2507.08138 (*cross-listing*)
Date: Thu, 10 Jul 2025 19:56:14 GMT (924kb)
Title: On Conservative Matrix Fields: Continuous Asymptotics and Arithmetic
Authors: Shachar Weinbaum, Elyasheev Leibtag, Rotem Kalisch, Michael Shalyt,
Ido Kaminer
Categories: math.NT cs.SC math.CO math.RA
Comments: 26 pages, 5 figures
MSC-class: 11J70, 11J82, 40A15, 33C80, 33C70, 68W30
\\
Ratios of D-finite sequences and their limits -- known as Ap\'ery limits --
have driven much of the work on irrationality proofs since Ap\'ery's 1979
breakthrough proof of the irrationality of $\zeta(3)$. We extend ratios of
D-finite sequences to a high-dimensional setting by introducing the
Conservative Matrix Field (CMF). We demonstrate how classical Ap\'ery limits
are included by this object as special cases. A useful construction of CMFs is
provided, drawing a connection to gauge transformations and to representations
of shift operators in finite dimensional modules of Ore algebras. Finally,
numerical experiments on these objects reveal surprising arithmetic and
dynamical phenomena, which are formulated into conjectures. If established,
these conjectures would extend Poincar\'e--Perron asymptotics to higher
dimensions, potentially opening the door to optimization-based searches for new
irrationality proofs.
\\ ( https://arxiv.org/abs/2507.08138 , 924kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08560 (*cross-listing*)
Date: Fri, 11 Jul 2025 13:01:39 GMT (8453kb)
Title: Domino Tilings of the Aztec Diamond in Random Environment and Schur
Generating Functions
Authors: Alexey Bufetov, Leonid Petrov, Panagiotis Zografos
Categories: math.PR cond-mat.stat-mech math-ph math.CO math.MP
Comments: 33 pages, 7 figures. Interactive simulation is available at
https://lpetrov.cc/simulations/2025-06-25-random-edges/
MSC-class: 60K35, 82B20, 05E05, 60C05, 60F05, 82B44
\\
We study the asymptotic behavior of random domino tilings of the Aztec
diamond of size $M$ in a random environment, where the environment is a
one-periodic sequence of i.i.d. random weights attached to domino positions
(i.e., to the edges of the underlying portion of the square grid). We consider
two cases: either the variance of the weights decreases at a critical scale
$1/M$, or the distribution of the weights is fixed. In the former case, the
unrescaled fluctuations of the domino height function are governed by the sum
of a Gaussian Free Field and an independent Brownian motion. In the latter
case, we establish fluctuations on the much larger scale $\sqrt M$, given by
the Brownian motion alone.
To access asymptotic fluctuations in random environment, we employ the method
of Schur generating functions. Moreover, we substantially extend the known Law
of Large Numbers and Central Limit Theorems for particle systems via Schur
generating functions in order to apply them to our setting. These results might
be of independent interest.
\\ ( https://arxiv.org/abs/2507.08560 , 8453kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08646 (*cross-listing*)
Date: Fri, 11 Jul 2025 14:50:34 GMT (6kb)
Title: Additive sumset sizes with tetrahedral differences
Authors: Melvyn B. Nathanson
Categories: math.NT math.CO
Comments: 7 pages
MSC-class: 11B13, 11B05, 11B75, 11P70, 11Y16, 11Y55
\\
Experimental calculations suggest that the $h$-fold sumset sizes of 4-element
sets of integers are concentrated at $h$ numbers that are differences of
tetrahedral numbers. In this paper it is proved that these "popular" sumset
sizes exist and explicit $h$-adically defined sets are constructed for each of
these numbers.
\\ ( https://arxiv.org/abs/2507.08646 , 6kb)
------------------------------------------------------------------------------
\\
arXiv:2507.08777 (*cross-listing*)
Date: Fri, 11 Jul 2025 17:39:52 GMT (11kb)
Title: Associated primes of the second power of closed neighborhood ideals of
graphs
Authors: Ha Thi Thu Hien, Thanh Vu
Categories: math.AC math.CO
MSC-class: 13C15, 13F55
\\
We study simple graphs for which the maximal homogeneous ideal is an
associated prime of the second power of their closed neighborhood ideals. In
particular, we show that such graphs must have diameter at most $6$, and that
those with diameter $2$ must be vertex diameter-$2$-critical.
\\ ( https://arxiv.org/abs/2507.08777 , 11kb)
%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%
------------------------------------------------------------------------------
\\
arXiv:2311.01945
replaced with revised version Fri, 11 Jul 2025 05:18:27 GMT (152kb)
Title: Closure property of contraction-depth of matroids
Authors: Marcin Brianski and Daniel Kral and Ander Lamaison
Categories: math.CO cs.DM
\\ ( https://arxiv.org/abs/2311.01945 , 152kb)
------------------------------------------------------------------------------
\\
arXiv:2401.12655
replaced with revised version Fri, 11 Jul 2025 12:16:17 GMT (58kb)
Title: Cokernel statistics for walk matrices of directed and weighted random
graphs
Authors: Alexander Van Werde
Categories: math.CO math.PR
Comments: 19 pages
MSC-class: 05C50, 15B52, 60B20
Journal-ref: Combinator. Probab. Comp. 34 (2025) 131-150
DOI: 10.1017/S0963548324000312
\\ ( https://arxiv.org/abs/2401.12655 , 58kb)
------------------------------------------------------------------------------
\\
arXiv:2404.06445
replaced with revised version Fri, 11 Jul 2025 16:39:33 GMT (45kb)
Title: Extremal minimal bipartite matching covered graphs
Authors: Amit Kumar Mallik, Ajit A. Diwan and Nishad Kothari
Categories: math.CO cs.DM
Comments: Accepted for publication in the Journal of Combinatorics on 13th June
2025. However, due to the journal's backlog, we are making the final accepted
version available here with permission from the journal's editors. The last
section (that is, Section 8) is new (in comparison to previous versions of
this manuscript)
\\ ( https://arxiv.org/abs/2404.06445 , 45kb)
------------------------------------------------------------------------------
\\
arXiv:2411.10394
replaced with revised version Thu, 10 Jul 2025 23:30:45 GMT (43kb)
Title: Tropical combinatorics of max-linear Bayesian networks
Authors: Carlos Am\'endola and Kamillo Ferry
Categories: math.CO math.AG math.ST stat.TH
Comments: 22 pages, 8 figures, 1 table
MSC-class: 05C12, 14T90, 52B11, 62R01
\\ ( https://arxiv.org/abs/2411.10394 , 43kb)
------------------------------------------------------------------------------
\\
arXiv:2502.07310
replaced with revised version Fri, 11 Jul 2025 07:39:45 GMT (32kb)
Title: Total $k$-coalition: bounds, exact values and an application to double
coalition
Authors: Bo\v{s}tjan Bre\v{s}ar and Sandi Klav\v{z}ar and Babak Samadi
Categories: math.CO
\\ ( https://arxiv.org/abs/2502.07310 , 32kb)
------------------------------------------------------------------------------
\\
arXiv:2503.20550
replaced with revised version Fri, 11 Jul 2025 10:37:26 GMT (121kb)
Title: On the order of the shortest solution sequences for the pebble motion
problems
Authors: Tomoki Nakamigawa and Tadashi Sakuma
Categories: math.CO cs.CC cs.DM
\\ ( https://arxiv.org/abs/2503.20550 , 121kb)
------------------------------------------------------------------------------
\\
arXiv:2504.16205
replaced with revised version Fri, 11 Jul 2025 08:03:26 GMT (442kb)
Title: All generalized rose window graphs are hamiltonian
Authors: Simona Bonvicini, Toma\v{z} Pisanski and Arjana \v{Z}itnik
Categories: math.CO
Comments: 28 pages, 9 figures
MSC-class: 05C45, 05C76, 05C70, 05C25, 05E18
\\ ( https://arxiv.org/abs/2504.16205 , 442kb)
------------------------------------------------------------------------------
\\
arXiv:2506.08883
replaced with revised version Thu, 10 Jul 2025 18:22:34 GMT (65kb)
Title: Factorizations in Hecke algebras I: long cycle factorizations and
Jucys-Murphy elements
Authors: Jose Bastidas, Sarah Brauner, Mathieu Guay-Paquet, Alejandro H.
Morales, GaYee Park, Franco Saliola
Categories: math.CO
Comments: minor edits
MSC-class: 20C08, 05A05, 05A15, 05A30, 05E05
\\ ( https://arxiv.org/abs/2506.08883 , 65kb)
------------------------------------------------------------------------------
\\
arXiv:2507.01851
replaced with revised version Fri, 11 Jul 2025 09:28:57 GMT (16kb)
Title: On the Visibility Polynomial of Graphs
Authors: Tonny K B, Shikhi M
Categories: math.CO
Comments: 12 pages, 3 figures, 1 table, 1 algorithm
MSC-class: 05C31, 05C39
\\ ( https://arxiv.org/abs/2507.01851 , 16kb)
------------------------------------------------------------------------------
\\
arXiv:2507.05473
replaced with revised version Fri, 11 Jul 2025 12:27:35 GMT (37kb)
Title: Counting with two-level polynomials
Authors: Tristram Bogart, Kevin Woods
Categories: math.CO
Comments: Corrected references, 35 pages
MSC-class: 05A99, 05C31, 52C07
\\ ( https://arxiv.org/abs/2507.05473 , 37kb)
------------------------------------------------------------------------------
\\
arXiv:2212.06819
replaced with revised version Fri, 11 Jul 2025 17:40:47 GMT (403kb)
Title: Determinantal random subgraphs
Authors: Adrien Kassel, Thierry L\'evy
Categories: math.PR math-ph math.CO math.MP
Comments: v3: New examples and references added; 73 pages, 13 figures, 1 table;
v2: Substantially revised and expanded; 68 pages, 11 figures, 1 table
MSC-class: 60C05, 05C31, 15A75, 05B35
\\ ( https://arxiv.org/abs/2212.06819 , 403kb)
------------------------------------------------------------------------------
\\
arXiv:2502.05322
replaced with revised version Thu, 10 Jul 2025 23:47:54 GMT (58kb)
Title: Tropical Fr\'echet Means
Authors: Bo Lin, Kamillo Ferry, Carlos Am\'endola, Anthea Monod, Ruriko Yoshida
Categories: math.OC math.CO math.MG math.ST stat.TH
Comments: 18 pages. 5 figures. v2: fixed a couple of typos
MSC-class: 14T90, 62R01, 62R20, 90C24
DOI: 10.1145/3747199.3747567
\\ ( https://arxiv.org/abs/2502.05322 , 58kb)
%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---
For general information on the new math archive (partitioned by
keyword subject classification), see http://arxiv.org/new/math.html
For subscribe options to combined math archives,
e-mail To: math@arxiv.org, Subject: subscribe
