Papers

For a graph G, its bondage number b(G) is the minimum number of edges whose deletion increases its domination number. Dunbar, Haynes, Teschner, and Volkmann conjectured in 1998 that every nontrivial planar graph satisfies b(G) <= Delta(G) + 1. We show that the truncated octahedral graph T has gamma(T) = 8 and b(T) = 5. Since T is planar and cubic, this gives b(T) = 5 > 4 = Delta(T) + 1 and disproves the conjecture. The finite parts of the verification are exhaustive: the direct verifier checks candidate dominating sets of sizes six, seven, and eight and all 58,905 four-edge sets. The targeted discovery search and an independently written verifier are described, and the complete C++20 verifier is included in the source archive.

Determining the dimension of the $C^1$ cubic spline space $S_3^1(\mathcal{T})$ on an arbitrary nondegenerate planar triangulation has remained unresolved since the 1970s. Schumaker's lower bound includes a local correction $\sigma$ for singular interior four-stars, and it was conjectured that this bound is always attained. We disprove this conjecture by constructing a one-parameter family of nondegenerate realizations of a fixed 18-triangle complex, with only the central vertex moving as $v_6(t)=(t,0)$ on the admissible interval $I=(-3/4,24/55)$. The family exhibits three distinct cases. For $t\in I\setminus\{1/5,3/83\}$, the lower bound is attained and $\dim S_3^1(\mathcal{T}(t))=33$. At $t=3/83$, the central four-star is singular, $\sigma=1$, and the resulting dimension 34 is exactly accounted for by the classical local correction. At $t=1/5$, however, all interior vertices are nonsingular and $\sigma=0$, yet $\dim S_3^1(\mathcal{T}(1/5))=34>P_{\mathcal{T}(1/5)}(1,3)=33$. The smoothing-cofactor calculation shows that the dependence at $t=3/83$ is confined to the central vertex block, whereas the dependence at $t=1/5$ couples all seven interior vertex cycles even though every individual block has full row rank. A complementary Bernstein–Bézier calculation gives the same dimension profile. Thus the singular-four-star correction does not capture every geometry-dependent contribution to $\dim S_3^1(\mathcal{T})$; genuinely global compatibility must also be taken into account.

We show the number of connected components of the Hilbert scheme of orthogonal Grassmannians under certain condition, and use this result to describe the geometry of the Hilbert scheme. Subsequently, we determine the Nef cone of the Hilbert scheme by identifying curves dual to the generators of its Neron-Severi group. Our results generalize those of ordinary Grassmannians by Seong, and our approach adapts his proof technique alongside relevant Schubert calculus.

We study the parity-perturbed Hofstadter $Q$-recursion $$ \widetilde Q(1)=\widetilde Q(2)=1,\qquad \widetilde Q(n)=\widetilde Q(n-\widetilde Q(n-1)) +\widetilde Q(n-\widetilde Q(n-2))+(-1)^n, $$ and the associated two-variable Dirichlet series $$ Z_{\widetilde Q}(s,t)=\sum_{n\ge1}n^{-s}\widetilde Q(n)^{-t}. $$ The estimate $\widetilde Q(n)=n/2+O(n/\sqrt{\log n})$ gives the exact domain of absolute convergence $\operatorname{Re}(s+t)>1$. With $w=s+t$, we separate the universal term $2^t\zeta(w)$ and derive exact transport, frequency-position, and dyadic renormalization identities. The main result concerns $t=-1$. For $E(n)=2\widetilde Q(n)-n$ and $A(X)=\sum_{n\le X}E(n)$, the binary-arch clock yields $$ A(X)=X\log_2X+X\Omega\!\left(\log_2\frac{3X}{32}\right) +O\!\left(\frac{X}{\sqrt{\log X}}\right), $$ where $\Omega$ is an explicit continuous periodic function. This continues the normalized correction to $\operatorname{Re}w>0$ and yields a boundary resonance lattice: a double resonance at $w=0$ and simple resonances at $2\pi i m/\log2$. After subtracting the full-slice order-$X$ skeleton, we analyze the negative-even arch channel. Its companion-forest layers have a weak Gaussian limit, and a canonical subsequence realizes the optimal $n/\sqrt{\log n}$ pointwise scale with an explicit signed constant. The negative-arch mass satisfies $$ A_r=\frac{512}{9\sqrt{2\pi}}\frac{16^r}{\sqrt r} \left(1-\frac{13}{16r}+O(r^{-2})\right). $$ We do not claim a full-slice continuation across $\operatorname{Re}w=0$.

An edge card of a graph is obtained by deleting one edge, and a class edge-reconstruction number asks for the fewest carefully selected cards that identify the graph when its class is known. We determine the sharp universal bound for maximal planar graphs. Two selected cards always suffice, and the octahedral graph shows that two can be necessary; some maximal planar graphs are already identified by one card. The argument exploits the fact that deleting a flippable edge leaves a single quadrilateral whose two diagonals give the only possible maximal-planar completions. Degree information then rules out the competing completion, with a separate argument for graphs containing a vertex of degree three. This settles a problem posed in a 2010 survey on reconstruction numbers.

We endow spaces of decorated planar rooted trees with new dendriform and tridendrifrom algebra structures and provide their combinatorial description. We then show that the planar counterparts of Arborified Zeta Values are algebra morphisms for these shuffle and quasi-shuffle products of planar rooted trees. We also prove an arborified version of Hoffman's regularisation relation for Arborified Zeta Values. We conjecture that those give every rational relation between Arborified Zeta Values and show that this conjecture implies the regularised double shuffle conjecture for Multiple Zeta Values.

Benjamini and Tzalik obtained an upper bound on the number of shortest paths between two vertices at distance $t$ in a multigraph of maximum degree at most $\Delta$, and proposed a conjecture on the sharp bound. In this paper, we develop a probabilistic counting argument based on probability distributions induced by random walks from the two endpoints. This approach yields a sharp bound for multigraphs and confirms their conjecture. We further determine the exact maximum for simple graphs and thus answer another question of Benjamini and Tzalik. We also investigate the equality cases, describing the structure of the subgraph formed by shortest paths between $x$ and $y$ and giving tight examples.

Let $P=\{0,a,b\}$, where $0<a<b$ and $\gcd(a,b)=1$. For a finite set $A\subset\mathbb Z$, let $M_P^+(A)$ count the copies $x,x+ad,x+bd\in A$ with $d>0$, and let $M_P(A)$ count the copies with any $d\ne0$. We prove that every such three-point pattern other than the arithmetic progression $\{0,1,2\}$ satisfies \[ M_P^+(A)\le \frac{99}{400}|A|^2+O(|A|), \qquad M_P(A)\le \frac{13}{28}|A|^2+O_P(|A|). \] For the particular pattern $P=\{0,1,3\}$ – the subject of a question raised by Ganguly and recorded as Problem 24 in Green's list of open problems – we sharpen the bound allowing both signs of the dilation to \[ M_{\{0,1,3\}}(A)\le \frac{47}{122}|A|^2+O(|A|). \]

The graph coloring game is a two-player game in which the players alternately color an uncolored vertex of a graph $G$. The game chromatic number is the minimum number of colors needed for the first player to guarantee a win. We investigate this parameter for generalized Mycielski graphs $M_k(G)$, where $G$ is a path $P_n$ or a cycle $C_n$ with $n$ vertices. For every $k\geq2$ and $n\geq5$, we establish $4\leq\chi_g\bigl(M_k(P_n)\bigr)\leq5$ and $4\leq\chi_g\bigl(M_k(C_n)\bigr)\leq5$. We also determine the exact values $\chi_g\bigl(M_2(P_5)\bigr)=\chi_g\bigl(M_2(P_6)\bigr)=4$. The proofs of the lower bounds use a configuration in which Bob can create two threats simultaneously, while the four-color upper bounds in the two exact cases are proved using the double-doctor lemma. Thus the number of layers and the order of the base graph may grow, but the game chromatic number remains bounded by five.

We study the graph $\mathcal{AO}(G)$ of acyclic orientations of a graph $G$. Two acyclic orientations are adjacent in this graph if they disagree on the orientation of a single arc. In particular, we focus on the Hamiltonicity of the graphs $\mathcal{AO}(G)$. Using two methods of pattern lacing which generalize the zig-zag method of Brenner, Cardinal, McConville, Merino and Mütze, we characterize which multipaths are $\mathcal{AO}$-Hamiltonian. Moreover, we give a criterion for the gluing of a multipath on a given graph to preserve $\mathcal{AO}$-Hamiltonicity. Building towards an inductive certification of $\mathcal{AO}$-Hamiltonicity via the (open) ear decomposition of 2-connected graphs, we propose three ways of gluing several multipaths to a given graph. In addition, we define the acyclic polynomials to encapsulate both the number of acyclic orientations of a graph and the "parity problem" proposed by Savage, Squire and West: if $-1$ is not a root of the acyclic polynomial of $G$, then $G$ is not $\mathcal{AO}$-Hamiltonian. We explore numerous properties of the acyclic polynomials, proving that they are not instances of the famous Tutte-Whitney polynomials, but that they too exhibit a partial deletion-contraction phenomenon.

Cycles $C_1,\ldots,C_k$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V(C_k)\subseteq\cdots\subseteq V(C_1)$, and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let $f_k(n)$ be the least number of edges that forces such a family in every $n$-vertex graph. Gil Fernández, Kim, Kim and Liu proved that $f_2(n)=O(n)$, answering a question of Erdős, and asked whether $f_k(n)=O_k(n)$ for every fixed $k$. We prove this for all $k$. The proof selects the inner cycles together with a disjoint subgraph that supplies their external neighbours. A reselection argument gives disjoint paths from every inner-cycle vertex to any sufficiently large target set. Sublinear expansion and a rooted clique minor then allow the vertices to be joined in the required cyclic order.

We prove two simple bivariate recurrences for the number of permutations with a long increasing subsequence. The two recurrences imply D-finiteness of the sequence in a certain range. As a consequence, we also obtain a proof of a conjecture posed by Kauers and Koutschan in 2023.

We construct an infinite family of Neumaier graphs of coherent rank five, answering the existence question at the smallest possible coherent rank beyond the strongly regular case. For every prime power $q\geqslant7$ with $q\equiv3\pmod4$, set $n=q+1$. Each graph in our construction has precisely five distinct eigenvalues, Neumaier parameters \[ \left( n(n-1)(n-3), \frac{n^2(n-3)}2, \frac{n(n^2-n-8)}4; \frac{(n-2)^2}{2}, (n-1)(n-3) \right), \] and its adjacency matrix lies in the Bose–Mesner algebra of the four-class association scheme of Holzmann, Kharaghani, and Suda. Paley Hadamard matrices and Desarguesian mutually orthogonal Latin squares yield an infinite family whose smallest member has parameters $(280,160,96;18,35)$.

Let $0 < \alpha \leq 1/2$. We say that a finite point set $P$ in $\mathbb{R}^d$ is $\alpha$-split by a hyperplane $h$ if each of the closed half-spaces determined by $h$, contains at least $\alpha |P|$ of the points of $P$. We further say $P$ is $\alpha$-split by a $k$-dimensional flat $\tau$ if $P$ is $\alpha$-split by any hyperplane through $\tau$. In the standard notation (which coincides with Tukey depth for $k= 0$), the $k$-flat $\tau$ has depth $\alpha$ with respect to $P$. We establish interesting Helly-type theorems for splitting families of finite point sets in $\mathbb{R}^d$. Unlike the classical sufficient Helly-type criteria for transversals to families of compact convex sets, which exist only for point and hyperplanes, our results extend to splitting families of point sets by collections of $k$-flats of arbitrary dimensionality $ 0 \leq k \leq d-1$.

The weakly zero-divisor graph $W\Gamma(R)$ of a commutative ring $R$ is the simple undirected graph whose vertices are nonzero zero-divisors of $R$, and two distinct vertices $x$, $y$ are adjacent if and only if there exists $w\in {\rm ann}(x)$ and $ z\in {\rm ann}(y)$ such that $wz =0$. In this paper, first we prove that the vertex connectivity of $W\Gamma(R)$ is equal to its minimum degree, where $R$ is either an Artinian ring or reduced ring. For any finite ring $R$, we obtain the vertex connectivity of $W\Gamma(R)$. Moreover, this paper characterizes all the vertices that attain the minimum degree of $W\Gamma(R)$.

The basis number $bn(G)$ of a graph $G$ is the minimum edge-congestion of a basis of its cycle space. We prove that every finite $n$-vertex multigraph satisfies $bn(G)=O(\log n)$, resolving, for simple graphs, a question of Bazargani, Biedl, Bose, Maheshwari and Miraftab, subsequently stated as a conjecture by Miraftab, Morin and Yuditsky. The argument also yields the cycle-rank refinement $bn(G)=O(\log \beta(G))$, where $\beta(G)$ is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then gives $bn(G)=O(\log g)$ for graphs of Euler genus $g$. For regular matroids we prove the ground-set bound $bn(M)=O(\log m)$, where $m=|E(M)|$, and logarithmic bounds in both the rank $r(M)$ and the cycle-space dimension $d$. All these orders are best possible.

Characterizations of lower and upper bounds for dual characters of flagged Weyl modules have attracted considerable interest. In this paper, we establish explicit pattern avoidance characterizations for lower and upper bounds of Schur characters, namely, the dual characters of Weyl modules associated with arbitrary diagrams. This setting extends the corresponding extremal problems for dual characters of flagged Weyl modules and includes skew Schur polynomials and, through Rothe diagrams, Stanley symmetric functions. Specifically, for a permutation $w$, we show that the Stanley symmetric function $F_w$ attains the lower bound if and only if $w$ avoids $321,2143,2413,3142$, and $3412$, and attains the upper bound if and only if $w$ avoids $312$ and $321$.

A subset $A\subseteq \mathbb N_0$ is $k$-AP covering if there exists a constant $n_0$ such that for every integer $x>n_0$, there exists $d\in\mathbb N_0$ such that $x-d, x-2d,\dots,x-(k-1)d$ are all in $A$. Disproving a conjecture of Kiss, Sándor, and Yang, we prove that for every integer $k\geq 6$, there exists a constant $\varepsilon=\varepsilon_k>0$ and a $k$-AP covering set $A$ such that $|A\cap \{0,1,\dots,n\}| < n^{\frac{k-2}{k-1}-\varepsilon}$ for all sufficiently large $n$. We also relate this problem to the Arithmetic Kakeya Conjecture by Katz and Tao.

We determine the measures (in the sense of Harman–Snowden) on the Fraïssé class of partially ordered sets: the space of measures is a union of a plane, eight lines, and 15 isolated points. This is the first case where the space is not equidimensional, and the first primitive case in which it has dimension at least two. ChatGPT was used to obtain many arguments. The writing was done entirely by the author.

For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).\] The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of $4$-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of $A$ has girth at least an even integer $g \geq 4$, then \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{2n/g}\operatorname{Bethe}(A).\] The upper bound is attained by the adjacency matrix of a disjoint union of $g$-cycles.

We present a new upper bound on the defect of the Mondrian Art Problem. The Mondrian Art Problem asks for a partition of an $n \times n$ square with rectangles of distinct dimensions such that the difference (defect) between the largest and smallest rectangle areas is minimized. We prove that for any $n \times n$ square, there exists a partition with defect $O(n^{5/6})$, improving upon the previously conjectured $O (n/\log n)$ upper bound. We also implement an algorithm that provides empirical evidence supporting our theoretical bound.

Let $H \sim H^{k}_c(n,p)$ be an edge-colored random $k$-uniform hypergraph on the vertex set $[n]$, where each edge $e \in \binom{[n]}{k}$ is included independently with probability $p$ and is uniformly and independently assigned a color from the color set $[c]$. For $k = 2$, Ferber and Krivelevich (2016) established that if $c = (1+o(1))n$ and $p = (\log n + \log \log n + \omega(n))/n$, then with high probability the edge-colored random graph $H \sim H^2_c(n,p)$ contains a rainbow Hamilton Berge cycle. Subsequently, Bal, Berkowitz, Devlin, and Schacht (2021) determined the threshold for the appearance of a (non-rainbow) Hamilton Berge cycle in random $k$-uniform hypergraphs. In this paper, we generalize the results to all integers $k \ge 3$. We prove that if $c = (1+o(1))n$ and $p = (k-1)! \frac{\log n + \log\log n + \omega(n)}{n^{k-1}}$, then with high probability $H \sim H^{k}_c(n,p)$ contains a rainbow Hamilton Berge cycle. Furthermore, both conditions on $c$ and $p$ are asymptotically tight. \noindentKey words: Rainbow subgraph, Hamiltonicity, Berge cycle, Random hypergraph.

For a finite simple graph $G$ with at least one edge, the bondage number $b(G)$ is the least number of edges whose deletion increases the domination number $\gamma(G)$. Teschner conjectured that $b(G)\le \tfrac32\Delta(G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ \gamma(G)=6 \qquad\text{and}\qquad b(G)=5. \] The domination number is established by a complete counting argument across the bipartition. An explicit five-edge deletion raises the domination number from six to seven. For the matching lower bound, we give an exact finite certificate: the graph has 297 minimum dominating sets, and deleting any one of its $\binom{27}{4}=17{,}550$ four-edge subsets leaves at least one of those sets dominating. The enumeration is deterministic, uses only exact integer and set operations, and is reproduced by the complete standard-library verifier included in the appendix.

The power graph of a finite group $G$ is a simple undirected graph with vertex set $G$ and two vertices are adjacent if one is a power of the other. The intersection power graph of a finite group $G$ is a simple undirected graph with vertex set $G$ and two vertices $x$, $y$ are adjacent if $\langle x\rangle \cap \langle y \rangle \neq \{e\}$. The difference graph $\mathcal{D}(G)$ of a finite group $G$ is the difference of the intersection power graph and power graph with all isolated vertices removed. We characterized all the finite nilpotent groups $G$ except $2$-group such that the difference graph is planar. Further, we determine all the finite nilpotent groups whose difference graph has genus at most $2$. Moreover, we prove that there does not exist any finite group whose difference graph is projective planar.

The book with $t$ pages is the graph on $t+2$ vertices consisting of $t$ triangles which intersect at exactly one common edge. For a given graph $F$, the $r$-expansion $F^r$ of $F$ is the $r$-uniform hypergraph obtained from $F$ by adding $r-2$ distinct new vertices to each edge of $F$. We determine the Turán number of the 3-expansion of the book graph for sufficiently large $n$.

A graph $G$ is perfect if $\omega(H) = \chi(H)$ for each induced subgraph $H$ of $G$. In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem. Motivated by this forbidden induced subgraph characterization of the class of perfect graphs as well as the possible extension of efficient algorithms on perfect graphs, we consider the structure of graphs that are almost perfect. We say a graph is $c$-apex perfect if there is a constant $c$ number of vertices such that, upon the deletion of these vertices, what remains is a perfect graph. In this paper, we characterize the class of the sets of graphs $\mathcal{H}$ with $|\mathcal{H}|\leq 2$ for which there exists $c \in \mathbb{N}$ with the property that each $\mathcal{H}$-free graph is $c$-apex perfect. We also extend these results to several notable subclasses of perfect graphs, including chordal, interval, split, bipartite, and complete multipartite graphs.

For finite simple graphs $G,H$ on a common vertex set $V$, we say that $H$ is $G$-colorable if $H$ admits a proper list coloring with list assignment $L(v)=N_G(v)$ for all $v\in V$. This notion of coloring a graph using the neighborhood of another graph on the same vertex set, which we call graphic list coloring, has connections to several classical topics, including systems of distinct representatives and graph factorizations. In this paper, we investigate when a necessary Hall-type condition, introduced by Hilton and Johnson in 1990, is also sufficient for $H$ to be $G$-colorable. We characterize all graphs $H$ that are $G$-colorable whenever the pair $(H,G)$ satisfies Hall's condition, answering a question raised by Johnson. We then consider the dual problem of characterizing graphs $G$ such that, whenever $(H,G)$ satisfies Hall's condition, $H$ is $G$-colorable. In this vein, we obtain complete results for several families of graphs, such as forests, complete multipartite graphs, and grid graphs.

Let $G$ be a compact, connected, simply connected semisimple Lie group with Weyl group $W$ and simple reflections $S$. For a simplicial complex $\mathcal K$ on $S$, form the homotopy colimit $X_{\mathcal K}(G)=\operatorname*{hocolim}_{I\in\mathcal K}G/G_I$ of standard partial flag manifolds. We compute its integral homology. If $\operatorname{Des}_R(w)$ is the right descent set of $w\in W$ and $\ell(w)$ its Coxeter length, then $$ H_n(X_{\mathcal K}(G);\mathbb Z)\cong \bigoplus_{w\in W}\widetilde H_{n-2\ell(w)-1}(\mathcal K_{\operatorname{Des}_R(w)};\mathbb Z). $$ Thus the induced subcomplexes of $\mathcal K$ supply the topological data, while the Weyl group determines which subcomplex occurs and the Schubert-degree shift. The proof gives a chain-level splitting and an integral Morse reduction. We derive homotopy detection, duality and rigidity results, and recover polyhedral products, matroid–Tutte formulas, and the adjoint sphere as special cases.

For a graph $G$, a proper edge coloring of $G$ is called a D-coloring if every diamond subgraph of $G$ is rainbow. Let $\chi'_D(G)$ be the D-chromatic index of $G$, which is the smallest integer $k$ such that $G$ admits a D-coloring with $k$ colors. Let $\Delta$ be the maximum degree of $G$. The only known Brooks-type upper bound on $\chi'_D(G)$ is $\frac{9}{16}\Delta^2 + \frac{1}{2}\Delta$, given by a greedy coloring. In this paper, using a probabilistic method, we obtain the first improvement upon this upper bound by proving that $\chi'_D(G) \le (1-c)\frac{9}{16}\Delta^2$ for some $c > 0$ and sufficiently large $\Delta$.

We introduce a guessing game, “Permutation Wordle,” in which a guesser attempts to recover a setter's hidden permutation of the set $\{1, \ldots, n\}$. In each round, the guesser submits a word over the alphabet $\{1, \ldots, n\}$, and, as in the game Wordle, learns which entries are correct. We describe a natural strategy and prove that it is optimal in a strong sense: for every $r$, it solves at least as many secrets within $r$ rounds as any possible strategy. The number of permutations it solves in exactly $k+1$ rounds is the Eulerian number $A(n,k)$.