Date: Fri, 9 Aug 2024 | Total: 21

Strongly stable ideals are a class of monomial ideals which correspond to generic initial ideals in characteristic zero and can be described completely by their Borel generators, a subset of the minimal monomial generators of the ideal. Francisco, Mermin, and Schweig developed formulas for the Hilbert series and Betti numbers of strongly stable ideals in terms of their Borel generators. In this work, a specialization of strongly stable ideals is presented which further restricts the subset of relevant generators. A choice of weight vector $w\in\mathbb{N}_{> 0}^n$ restricts the set of strongly stable ideals to a subset designated as $w$-stable ideals. This restriction further compresses the Borel generators to a subset termed the weighted Borel generators of the ideal. A new Macaulay2 package wStableIdeals.m2 has been developed alongside this paper and segments of code support computations within.

Recently there has been several works estimating the number of $n\times n$ matrices with elements from some finite sets $\mathcal X$ of arithmetic interest and of a given determinant. Typically such results are compared with the trivial upper bound $O(X^{n^2-1})$, where $X$ is the cardinality of $\mathcal X$. Here we show that even for arbitrary sets $\mathcal X\subseteq \mathbb R$,some recent results from additive combinatorics enable us to obtain a stronger bound with a power saving.

Let $G_{n,k}$ be the group of permutations of $\{1,2,\ldots, kn\}$ that permutes the first $k$ symbols arbitrarily, then the next $k$ symbols and so on through the last $k$ symbols. Finally the $n$ blocks of size $k$ are permuted in an arbitrary way. For $\sigma$ chosen uniformly in $G_{n,k}$, let $L_{n,k}$ be the length of the longest increasing subsequence in $\sigma$. For $k,n$ growing, we determine that the limiting mean of $L_{n,k}$ is asymptotic to $4\sqrt{nk}$. This is different from parallel variations of the Vershik-Kerov theorem for colored permutations.

The paper considers implementations of some randomized algorithms in connection with obtaining a random $n^2 \times n^2$ Sudoku matrix with programming language C++. For this purpose we describes the set $\Pi_n$ of all $(2n) \times n$ matrices, consisting of elements of the set $\mathbb{Z}_n =\{ 1,2,\ldots ,n\}$, such that every row is a permutation. We emphasize the relationship between these matrices and the $n^2 \times n^2$ Sudoku matrices. An algorithm to obtain random $\Pi_n$ matrices is presented in this paper. Several auxiliary algorithms that are related to the underlying problem have been described. We evaluated all algorithms according to two criteria - probability evaluation, and time for generation of random objects and checking of belonging to a specific set. This evaluations are interesting from both theoretical and practical point of view because they are particularly useful in the analysis of computer programs.

In this paper, we first study what we call Superset-Subset-Disjoint (SSD) set system. Based on properties of SSD set system, we derive the following (I) to (IV): (I) For a nonnegative integer $k$ and a graph $G=(V,E)$ with $|V|\ge2$, let $X_1,X_2,\dots,X_q\subsetneq V$ denote all maximal proper subsets of $V$ that induce $k$-edge-connected subgraphs. Then at least one of (a) and (b) holds: (a) $\{X_1,X_2,\dots,X_q\}$ is a partition of $V$; and (b) $V\setminus X_1, V\setminus X_2,\dots,V\setminus X_q$ are pairwise disjoint. (II) For a strongly-connected (i.e., $k=1$) digraph $G$, we show that whether $V$ is in (a) and/or (b) can be decided in $O(n+m)$ time and that we can generate all such $X_1,X_2,\dots,X_q$ in $O(n+m+|X_1|+|X_2|+\dots+|X_q|)$ time, where $n=|V|$ and $m=|E|$. (III) For a digraph $G$, we can enumerate in linear delay all vertex subsets of $V$ that induce strongly-connected subgraphs. (IV) A digraph is Hamiltonian if there is a spanning subgraph that is strongly-connected and in the case (a).

We study nonnegative and sums of squares symmetric (and even symmetric) functions of fixed degree. We can think of these as limit cones of symmetric nonnegative polynomials and symmetric sums of squares of fixed degree as the number of variables goes to infinity. We compare these cones, including finding explicit examples of nonnegative polynomials which are not sums of squares for any sufficiently large number of variables, and compute the tropicalizations of their dual cones in the even symmetric case. We find that the tropicalization of the dual cones is naturally understood in terms of the overlooked superdominance order on partitions. The power sum symmetric functions obey this same partial order (analogously to how term-normalized power sums obey the dominance order).

Over fields of characteristic two, we construct an infinite ascending chain of GL-stable ideals in the coordinate ring of infinite (skew-)symmetric matrices. This construction provides the first known example of a non-noetherian GL-algebra, thereby resolving a long-standing open question in the area. Our results build on the work of Draisma, Krasilnikov, and Krone.

The concept of mutual visibility in graphs, introduced recently, addresses a fundamental problem in Graph Theory concerning the identification of the largest set of vertices in a graph such that any two vertices have a shortest path connecting them, excluding internal vertices of the set. Originally motivated by some challenges in Computer Science related to robot navigation, the problem seeks to ensure unobstructed communication channels between navigating entities. The mutual-visibility problem involves determining a largest mutual-visibility set in a graph. The mutual-visibility number of a graph represents the cardinality of the largest mutual-visibility set. This concept has sparked significant research interest, leading to connections with classical combinatorial problems like the Zarankiewicz problem and Tur\'an-type problems. In this paper, we consider practical limitations in network visibility and our investigation extends the original concept to $k$-distance mutual-visibility. In this case, a pair of vertices is considered $S$-visible if a shortest path of length at most $k$ exists, excluding internal vertices belonging to the set $S$. The $k$-distance mutual-visibility number represents the cardinality of a largest $k$-distance mutual-visibility set. We initiate the study of this new graph parameter. We prove that the associate decision problem belongs to the NP-complete class. We also give some properties and tight bounds, as well as, the exact value of such parameter for some particular non trivial graph classes.

Let $G$ be a connected graph on $n$ vertices and $1 \le k \le n-1$ an integer. The $k$-token graph of $G$ is the graph $F_k(G)$ whose vertices are all the $k$-subsets of vertices of $G$, two of which are adjacent whenever their symmetric difference is an edge of $G$. Every automorphism of $G$ induces an automorphism of $F_k(G)$ in a natural way. Suppose that $S:=\{x,y\}$ is a cut set of $G$, such that $x$ and $y$ have the same neighbours in $G\setminus \{x,y\}$. In this paper we show that there exist a large number of automorphisms of $F_k(G)$ defined by $S$ that are not induced by automorphisms of $G$. We also describe the group produced by all such $2$-cuts of $G$.

We construct an edge-colored digraph analogous to Mathon's construction for undirected graphs. We show that this graph is connected to the $k$-th power Paley digraphs and we use this connection to produce improved lower bounds for multicolor directed Ramsey numbers.

A Latin tableau of shape $\lambda$ and type $\mu$ is a Young diagram of shape $\lambda$ in which each box contains a single positive integer, with no repeated integers in any row or column, and the $i$th most common integer appearing $\mu_i$ times. Over twenty years ago, Chow et al., in their study of a generalization of Rota's basis conjecture that they called the wide partition conjecture, conjectured a necessary and sufficient condition for the existence of a Latin tableau of shape $\lambda$ and type $\mu$. We report some computational evidence for this conjecture, and prove that the conjecture correctly characterizes, for any given $\lambda$, at least the first four parts of $\mu$.

A family of $r$ distinct sets $\{A_1,\ldots, A_r\}$ is an $r$-sunflower if for all $1 \leqslant i < j \leqslant r$ and $1 \leqslant i' < j' \leqslant r$, we have $A_i \cap A_j = A_{i'} \cap A_{j'}$. Erd\H{o}s and Rado conjectured in 1960 that every family $\mathcal{H}$ of $\ell$-element sets of size at least $K(r)^\ell$ contains an $r$-sunflower, where $K(r)$ is some function that depends only on $r$. We prove that if $\mathcal{H}$ is a family of $\ell$-element sets of VC-dimension at most $d$ and $|\mathcal{H}| > (C r (\log d+\log^\ast \ell))^\ell$ for some absolute constant $C > 0$, then $\mathcal{H}$ contains an $r$-sunflower. This improves a recent result of Fox, Pach, and Suk. When $d=1$, we obtain a sharp bound, namely that $|\mathcal{H}| > (r-1)^\ell$ is sufficient. Along the way, we establish a strengthening of the Kahn-Kalai conjecture for set families of bounded VC-dimension, which is of independent interest.

A pair $(\mathrm{st_1}, \mathrm{st_2})$ of permutation statistics is said to be $r$-Euler-Mahonian if $(\mathrm{st_1}, \mathrm{st_2})$ and $( \mathrm{rdes}$, $\mathrm{rmaj})$ are equidistributed over the set $\mathfrak{S}_{n}$ of all permutations of $\{1,2,\ldots, n\}$, where $\mathrm{rdes}$ denotes the $r$-descent number and $\mathrm{rmaj}$ denotes the $r$-major index introduced by Rawlings. The main objective of this paper is to prove that $(\mathrm{exc}_r, \mathrm{den}_r)$ and $( \mathrm{rdes}$, $\mathrm{rmaj})$ are equidistributed over $\mathfrak{S}_{n}$, thereby confirming a recent conjecture posed by Liu. When $r=1$, the result recovers the equidistribution of $(\mathrm{des}, \mathrm{maj})$ and $(\mathrm{exc}, \mathrm{den})$, which was first conjectured by Denert and proved by Foata and Zeilberger.

We consider extremal edge-coloring problems inspired by the theory of anti-Ramsey / rainbow coloring, and further by odd-colorings and conflict-free colorings. Let $G$ be a graph, and $F$ any given family of graphs. For every integer $n \geq |G|$, let $f(n,G|F)$ denote the smallest integer $k$ such that any edge coloring of the complete graph $K_n$ with at least $k$ colors forces a copy of $G$ in which each color class induces a member of $F$. Observe that in anti-Ramsey problems each color class is a single edge; i.e., $F=\{K_2\}$. In our previous paper [arXiv:2405.19812], attention was given mostly to the case where $F$ is hereditary under subgraph inclusion. In the present work we consider coloring problems inspired by odd-coloring and conflict-free coloring. As we shall see, dealing with these problems requires distinct additional tools to those used in our first paper on the subject. Among the many results introduced in this paper, we mention: (1) For every graph $G$, there exists a constant $c=c(G)$ such that in any edge coloring of $K_n$ with at least $cn$ colors there is a copy of $G$ in which every vertex $v$ is incident with an edge whose color appears only once among all edges incident with $v$. (2) In sharp contrast to the above result we prove that if $F$ is the class of all odd graphs (having vertices with odd degrees only) then $f(n,K_k|F)=(1+o(1))$ex$(n,K_{\lceil k/2 \rceil})$, which is quadratic for $k \geq 5$. (3) We exactly determine $f(n,G|F)$ for small graphs when $F$ belongs to several families representing various odd/even coloring constraints.

Assume that $R_1,R_2,\dots,R_t$ are disjoint parallel lines in the plane. A $t$-interval (or $t$-track interval) is a set that can be written as the union of $t$ closed intervals, each on a different line. It is known that pairwise intersecting $2$-intervals can be pierced by two points, one from each line. However, it is not true that every set of pairwise intersecting $3$-intervals can be pierced by three points, one from each line. For $k\ge 3$, Kaiser and Rabinovich asked whether $k$-wise intersecting $t$-intervals can be pierced by $t$ points, one from each line. Our main result provides an asymptotic answer: in any set $S_1,\dots,S_n$ of $k$-wise intersecting $t$-intervals, at least $\frac{k-1}{k+1}n$ can be pierced by $t$ points, one from each line. We prove this in a more general form, replacing intervals by subtrees of a tree. This leads to questions and results on covering vertices of edge-colored complete graphs by vertices of monochromatic cliques having distinct colors, where the colorings are chordal, or more generally induced $C_4$-free graphs. For instance, we show that if the edges of a complete graph $K_n$ are colored with red or blue so that both color classes are induced $C_4$-free, then at least ${4n\over 5}$ vertices can be covered by a red and a blue clique, and this is best possible. We conclude by pointing to new Ramsey-type problems emerging from these restricted colorings.

For a graph $G$, we call an edge coloring of $G$ an \textit{improper} \textit{interval edge coloring} if for every $v\in V(G)$ the colors, which are integers, of the edges incident with $v$ form an integral interval. The \textit{interval coloring impropriety} of $G$, denoted by $\mu_{int}(G)$, is the smallest value $k$ such that $G$ has an improper interval edge coloring where at most $k$ edges of $G$ with a common endpoint have the same color. The purpose of this note is to communicate solutions to two previous questions on interval coloring impropriety, mainly regarding planar graphs. First, we prove $\mu_{int}(G) \leq 2$ for every outerplanar graph $G$. This confirms the conjecture by Casselgren and Petrosyan in the affirmative. Secondly, we prove that for each $k\geq 2$, the interval coloring impropriety of $k$-trees is unbounded. This refutes the conjecture by Carr, Cho, Crawford, Ir\v{s}i\v{c}, Pai and Robinson.

For each $\nu\in \{1,2\}$, we examine the set $\mathscr{U}_{x,y}^\nu$ of all formal bivariate Laurent series $f(x,y)=\sum_{i,j\in\mathbb{Z}}c_{ij}x^iy^j$ such that $c_{i,j}=c_{-i,j}$ and $c_{i,j}\ge c_{i+\nu, j}\ge 0$ for all non-negative integers $i$ and all integers $j$. We show that the set $\mathscr{U}_{x, y}^\nu$ forms a commutative semiring under the operations of addition and multiplication of formal Laurent series. This result is used to establish the unimodality of sequences involving Gauss polynomials and certain refined color partitions. In particular, we solve an open problem posed by Andrews on the unimodality of generalized Gauss polynomials and establish an unimodal result for a statistic of plane partitions. We also establish many unimodal results for rank statistics in partition theory, including the rank statistics of concave and convex compositions studied by Andrews, as well as certain unimodal sequences studied by Kim-Lim-Lovejoy. Additionally, we establish the unimodality of the Betti numbers and Gromov-Witten invariants of certain Hilbert schemes of points.

In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. In particular, critical and list-critical graphs occupy a prominent place in graph coloring theory. Stiebitz, Tuza, and Voigt introduced strongly critical graphs, i.e., graphs that are $k$-critical yet $L$-colorable with respect to every non-constant assignment $L$ of lists of size $k-1$. Here we strengthen this notion and extend it to the framework of DP-coloring (or correspondence coloring) by defining robustly $k$-critical graphs as those that are not $(k-1)$-DP-colorable, but only due to the fact that $\chi(G) = k$. We then seek general methods for constructing robustly critical graphs. Our main result is that if $G$ is a critical graph (with respect to ordinary coloring), then the join of $G$ with a sufficiently large clique is robustly critical; this is new even for strong criticality.

We provide sufficient conditions for a regular graph $G$ of growing degree $d$, guaranteeing a phase transition in its random subgraph $G_p$ similar to that of $G(n,p)$ when $p\cdot d\approx 1$. These conditions capture several well-studied graphs, such as (percolation on) the complete graph $K_n$, the binary hypercube $Q^d$, $d$-regular expanders, and random $d$-regular graphs. In particular, this serves as a unified proof for these (and other) cases. Suppose that $G$ is a $d$-regular graph on $n$ vertices, with $d=\omega(1)$. Let $\epsilon>0$ be a small constant, and let $p=\frac{1+\epsilon}{d}$. Let $y(\epsilon)$ be the survival probability of a Galton-Watson tree with offspring distribution Po$(1+\epsilon)$. We show that if $G$ satisfies a (very) mild edge expansion requirement, and if one has fairly good control on the expansion of small sets in $G$, then typically the percolated random subgraph $G_p$ contains a unique giant component of asymptotic order $y(\epsilon)n$, and all the other components in $G_p$ are of order $O(\log n/\epsilon^2)$. We also show that this result is tight, in the sense that if one asks for a slightly weaker control on the expansion of small sets in $G$, then there are $d$-regular graphs $G$ on $n$ vertices, where typically the second largest component is of order $\Omega(d\log (n/d))=\omega(\log n)$.

Let $d\ge 3$ be a fixed integer. Let $y:= y(p)$ be the probability that the root of an infinite $d$-regular tree belongs to an infinite cluster after $p$-bond-percolation. We show that for every constants $b,\alpha>0$ and $1<\lambda< d-1$, there exist constants $c,C>0$ such that the following holds. Let $G$ be a $d$-regular graph on $n$ vertices, satisfying that for every $U\subseteq V(G)$ with $|U|\le \frac{n}{2}$, $e(U,U^c)\ge b|U|$ and for every $U\subseteq V(G)$ with $|U|\le \log^Cn$, $e(U)\le (1+c)|U|$. Let $p=\frac{\lambda}{d-1}$. Then, with probability tending to one as $n$ tends to infinity, the largest component $L_1$ in the random subgraph $G_p$ of $G$ satisfies $\left|1-\frac{|L_1|}{yn}\right|\le \alpha$, and all the other components in $G_p$ are of order $O\left(\frac{\lambda\log n}{(\lambda-1)^2}\right)$. This generalises (and improves upon) results for random $d$-regular graphs.

We present progress on two old conjectures about longest cycles in graphs. The first conjecture, due to Thomassen from 1978, states that apart from a finite number of exceptions, all connected vertex-transitive graphs contain a Hamiltonian cycle. The second conjecture, due to Smith from 1984, states that for $r\ge 2$ in every $r$-connected graph any two longest cycles intersect in at least $r$ vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph which can be used to improve the best known bounds towards both of the aforementioned conjectures: First, we show that every connected vertex-transitive graph on $n\geq 3$ vertices contains a cycle of length at least $\Omega(n^{13/21})$, improving on $\Omega(n^{3/5})$ from [De Vos, arXiv:2302:04255, 2023]. Second, we show that in every $r$-connected graph with $r\geq 2$, any two longest cycles meet in at least $\Omega(r^{5/8})$ vertices, improving on $\Omega(r^{3/5})$ from [Chen, Faudree and Gould, J. Combin. Theory, Ser.~ B, 1998]. Our proof combines combinatorial arguments, computer-search and linear programming.