Search

The sphere graph of $M_r$, a connect sum of $r$ copies of $S^1\times S^2$ was introduced by Hatcher as an analog of the curve graph of a surface to study the outer automorphism group of a free group $F_r$. Bestvina, Bromberg, and Fujiwara proved that the chromatic number of the curve graph is finite; bounds were subsequently improved by Gaster, Greene, and Vlamis. Motivated by the analogy, we provide upper and lower bounds for the chromatic number of the sphere graph of $M_r$. As a corollary to the prime decomposition of 3-manifolds, this gives bounds on the chromatic number of the sphere graph for any orientable 3-manifold., Comment: 7 pages, 2 figures

For a graph $G$, and a nonnegative integer $g$, let $a_g(G)$ be the number of $2$-cell embeddings of $G$ in an orientable surface of genus $g$ (counted up to the combinatorial homeomorphism equivalence). In 1989, Gross, Robbins, and Tucker [Genus distributions for bouquets of circles, J. Combin. Theory Ser. B 47 (1989), 292-306] proposed a conjecture that the sequence $a_0(G),a_1(G),a_2(G),\dots$ is log-concave for every graph $G$. This conjecture is reminiscent to the Heron-Rota-Welsh Log Concavity Conjecture that was recently resolved in the affirmative by June Huh et al., except that it is closer to the notion of $\Delta$-matroids than to the usual matroids. In this short paper, we disprove the Log Concavity Conjecture of Gross, Robbins, and Tucker by providing examples that show strong deviation from log-concavity at multiple terms of their genus sequences.

Starting from the geometric construction of the framed braid group, we define and study the framization of several Brauer-type monoids and also the set partition monoid, all of which appear in knot theory. We introduce the concept of deframization, which is a procedure to obtain a tied monoid from a given framed monoid. Furthermore, we show in detail how this procedure works on the monoids mentioned above. We also discuss the framization and deframization of some algebras, which are deformations, respectively, of the framized and deframized monoids discussed here.

A hypergraph is conformal if it is the family of maximal cliques of a graph. In this paper we are interested in the problem of determining when is the family of minimal transversal of maximal cliques of a graph conformal. Such graphs are called clique dually conformal (CDC for short). As our main results, we completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. We also show that the class of CDC graphs is closed under substitution, in the strong sense that substituting a graph $H$ for a vertex of a graph $G$ results in a CDC graph if and only if both $G$ and $H$ are CDC.

Fix $k\geq 2$, choose $\frac{\log n}{n^{(k-1)/k}}\leq p\leq 1-\Omega(\frac{\log^4 n}{n})$, and consider $G\sim G(n,p)$. For any pair of vertices $v,w\in V(G)$, we give a simple and precise formula for the expected number of steps that a random walk on $G$ starting at $w$ needs to first arrive at $v$. The formula only depends on basic structural properties of $G$. This improves and extends recent results of Ottolini and Steinerberger, as well as Ottolini, who considered this problem for constant as well as for mildly vanishing $p$., Comment: 14 pages

We prove some new instances of a conjecture of Bachoc, Couvreur and Z\'emor that generalizes Freiman's $3k-4$ Theorem to a multiplicative version in a function field setting. As a consequence we find that if $F$ is a rational function field over an algebraically closed field $K$ and $S \subset F$ a finite dimensional $K$-vector space such that $\dim S^2 = 2\dim S + 1$, then the conjecture holds.

We review the notion of symplectic duality earlier introduced in the context of topological recursion. We show that the transformation of symplectic duality can be expressed as a composition of $x-y$ dualities in a broader context of log topological recursion. As a corollary, we establish nice properties of symplectic duality: various convenient explicit formulas, invertibility, group property, compatibility with topological recursion and KP integrability. As an application of these properties, we get a new and uniform proof of topological recursion for large families of weighted double Hurwitz numbers; this encompasses and significantly extends all previously known results on this matter., Comment: 28 pages

This paper is a contribution towards a solution for the longstanding open problem of classifying linear systems of conics over finite fields initiated by L. E. Dickson in 1908, through his study of the projective equivalence classes of pencils of conics in $\mathrm{PG}(2,q)$, for $q$ odd. In this paper a set of complete invariants is determined for the projective equivalence classes of webs and of squabs of conics in $\mathrm{PG}(2,q)$, both for $q$ odd and even. Our approach is mainly geometric, and involves a comprehensive study of the geometric and combinatorial properties of the Veronese surface in $\mathrm{PG}(5,q)$. The main contribution is the determination of the distribution of the different types of hyperplanes incident with the $K$-orbit representatives of points and lines of $\mathrm{PG}(5,q)$, where $K\cong\mathrm{PGL}(3,q)$, is the subgroup of $\mathrm{PGL}(6,q)$ stabilizing the Veronese surface.

The Union-Closed Sets Conjecture, often attributed to P\'eter Frankl in 1979, remains an open problem in discrete mathematics. It posits that for any finite family of sets $S\neq\{\emptyset\}$, if the union of any two sets in the family is also in the family, then $\underline{\text{there must exist an element that belongs to at least half of the member sets}}$. We will refer to the underlined text as the abundance condition. In 2001, David Reimer proved that the average set size of a union-closed family $S$ must be at least $\frac{1}{2}\log_{2}|S|$. When proving this result, he showed that a family being union-closed implies that the family satisfies certain conditions, which we will refer to as the Reimer's conditions. Therefore, as seen in the context of Tim Gowers' polymath project on the Union-Closed Sets Conjecture, it is natural to ask if all families that satisfy Reimer's conditions meet the abundance condition. A minimal counterexample to this question was offered by Raz in 2017. In this paper, we will discuss a general method to construct infinitely many such counterexamples with any fixed lower bound on the size of the member sets. Furthermore, we will discuss some properties related to these counterexamples, especially those focusing on how far these counterexamples are from being union-closed.

Let $(W, S)$ be a Coxeter system of rank $n$ and let $p_{(W, S)}(t)$ be its growth function. It is known that $p_{(W, S)}(q^{-1}) < \infty$ holds for all $n \leq q \in \mathbb{N}$. In this paper we will show that this still holds for $q = n-1$, if $(W, S)$ is $2$-spherical. Moreover, we will prove that $p_{(W, S)}(q^{-1}) = \infty$ holds for $q = n-2$, if the Coxeter diagram of $(W, S)$ is the complete graph. These two results provide a complete characterization of the finiteness of the growth function in the case of $2$-spherical Coxeter systems with complete Coxeter diagram., Comment: 11 pages

We consider the space $P$ of generic complex 5-degree polynomials. Critical values of such polynomial, i.e. four points in the complex plane, either are vertices of a convex quadrangle $Q$, or vertices of a triangle $T$ with one point inside $T$. The inverse image of $Q$ is a tree-like connected structure of five ovals (a cactus). The inverse image of $T$ is also a cactus, but of four ovals. Transformations of cacti of the first type into cacti of the second type and vice versa allow one to represent the space $P$ as a ribbon bipartite graph of genus 3., Comment: 4 pages, 10 figures

We relate invariants of torus knots to the counts of a class of lattice paths, which we call generalized Schr\"oder paths. We determine generating functions of such paths, located in a region determined by a type of a torus knot under consideration, and show that they encode colored HOMFLY-PT polynomials of this knot. The generators of uncolored HOMFLY-PT homology correspond to a basic set of such paths. Invoking the knots-quivers correspondence, we express generating functions of such paths as quiver generating series, and also relate them to quadruply-graded knot homology. Furthermore, we determine corresponding A-polynomials, which provide algebraic equations and recursion relations for generating functions of generalized Schr\"oder paths. The lattice paths of our interest explicitly enumerate BPS states associated to knots via brane constructions., Comment: 33 pages, 7 figures

The motion of a graph is the minimum number of vertices that are moved by a non-trivial automorphism. Equivalently, it can be defined as the minimal degree of its automorphism group (as a permutation group on the vertices). In this paper we develop some results on permutation groups (primitive and imprimitive) with small minimal degree. As a consequence of such results we classify vertex-transitive graphs whose motion is $4$ or a prime number.

It is shown that a normalized complex Hadamard matrix of order $6$ having three distinct columns, each containing at least one $-1$ entry necessarily belongs to the transposed Fourier family, or to the family of $2$-circulant complex Hadamard matrices. The proofs rely on solving polynomial system of equations by Gr\"obner basis techniques, and make use of a structure theorem concerning regular Hadamard matrices. As a consequence, members of these two families can be easily recognized in practice. In particular, one can identify complex Hadamard matrices appearing in known triplets of pairwise mutually unbiased bases in dimension $6$., Comment: 17 pages, preprint

For the generation of acyclic biological diagrams, from a graph-theoretical perspective, we introduce the relative diagrams of cyclic permutations with ramphoid and keratoid vertices of degree 2, which correspond to Motzkin and Dyck words/paths. The relation between these two types of diagrams, defines the generation of the first via the permutations of the second, which may be of assistance in the study and treatment of several biological problems.

We construct $\Delta$-operators $F[\Delta]$ on the space of almost symmetric functions $\mathscr{P}_{as}^{+}$. These operators extend the usual $\Delta$-operators on the space of symmetric functions $\Lambda \subset \mathscr{P}_{as}^{+}$ central to Macdonald theory. The $F[\Delta]$ operators are constructed as certain limits of symmetric functions in the Cherednik operators $Y_i$ and act diagonally on the stable-limit non-symmetric Macdonald functions $\widetilde{E}_{(\mu|\lambda)}(x_1,x_2,\ldots;q,t).$ Using properties of Ion-Wu limits, we are able to compute commutation relations for the $\Delta$-operators $F[\Delta]$ and many of the other operators on $\mathscr{P}_{as}^{+}$ introduced by Ion-Wu. Using these relations we show that there is an action of $\mathbb{B}_{q,t}^{\text{ext}}$ on almost symmetric functions which we show is isomorphic to the polynomial representation of $\mathbb{B}_{q,t}^{\text{ext}}$ constructed by Gonz\'{a}lez-Gorsky-Simental., Comment: 20 pages. arXiv admin note: text overlap with arXiv:2307.05864

We prove that a Coxeter group containing an element of finite order, which is generated by two non-commuting involutions, can not be embedded into the Riordan group., Comment: 13 pages

We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, (2) affine sources, and (3) local sources. We significantly generalize these results, and prove the following. 1. Low-degree polynomials extract from small families. We show that a random low-degree polynomial is a good low-error extractor for any small family of sources. In particular, we improve the positive result of Alrabiah, Chattopadhyay, Goodman, Li, and Ribeiro (ICALP 2022) for local sources, and give new results for polynomial sources and variety sources via a single unified approach. 2. Low-degree polynomials extract from sumset sources. We show that a random low-degree polynomial is a good extractor for sumset sources, which are the most general large family of sources (capturing independent sources, interleaved sources, small-space sources, and more). This extractor achieves polynomially small error, and its min-entropy requirement is tight up to a square. Our results on sumset extractors imply new complexity separations for linear ROBPs, and the tools that go into its proof have further applications, as well. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between randomness extractors. Using the first new tool, we strengthen and generalize the extractor impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024). Using the second, we show the existence of sumset extractors for min-entropy $k=O(\log(n/\varepsilon))$, resolving an open problem of Chattopadhyay and Liao (STOC 2022)., Comment: 42 pages

We prove the following variant of Helly's classical theorem for Hamming balls with a bounded radius. For $n>t$ and any (finite or infinite) set $X$, if in a family of Hamming balls of radius $t$ in $X^n$, every subfamily of at most $2^{t+1}$ balls have a common point, so do all members of the family. This is tight for all $|X|>1$ and all $n>t$. The proof of the main result is based on a novel variant of the so-called dimension argument, which allows one to prove upper bounds that do not depend on the dimension of the ambient space. We also discuss several related questions and connections to problems and results in extremal finite set theory and graph theory.

This paper represents a significant leap forward in the problem of enumerating vertex-transitive graphs. Recent breakthroughs on symmetry of Cayley (di)graphs show that almost all finite Cayley (di)graphs have the smallest possible automorphism group. Extending the scope of these results, we enumerate (di)graphs admitting a fixed semiregular group of automorphisms with m orbits. Moreover, we consider the more intricate inquiry of prohibiting arcs within each orbit, where the special case m = 2 is known as the problem of finding Haar graphical representations (HGRs). We significantly advance the understanding of HGRs by proving that the proportion of HGRs among Haar graphs of a finite nonabelian group approaches 1 as the group order grows. As a corollary, we obtain an improved bound on the proportion of DRRs among Cayley digraphs in the solution of Morris and the second author to the Babai-Godsil conjecture.

We study the problem of distinguishing between two independent samples $\mathbf{G}_n^1,\mathbf{G}_n^2$ of a binomial random graph $G(n,p)$ by first order (FO) sentences. Shelah and Spencer proved that, for a constant $\alpha\in(0,1)$, $G(n,n^{-\alpha})$ obeys FO zero-one law if and only if $\alpha$ is irrational. Therefore, for irrational $\alpha\in(0,1)$, any fixed FO sentence does not distinguish between $\mathbf{G}_n^1,\mathbf{G}_n^2$ with asymptotical probability 1 (w.h.p.) as $n\to\infty$. We show that the minimum quantifier depth $\mathbf{k}_{\alpha}$ of a FO sentence $\varphi=\varphi(\mathbf{G}_n^1,\mathbf{G}_n^2)$ distinguishing between $\mathbf{G}_n^1,\mathbf{G}_n^2$ depends on how closely $\alpha$ can be approximated by rationals: (1) for all non-Liouville $\alpha\in(0,1)$, $\mathbf{k}_{\alpha}=\Omega(\ln\ln\ln n)$ w.h.p.; (2) there are irrational $\alpha\in(0,1)$ with $\mathbf{k}_{\alpha}$ that grow arbitrarily slowly w.h.p.; (3) $\mathbf{k}_{\alpha}=O_p(\frac{\ln n}{\ln\ln n})$ for all $\alpha\in(0,1)$. The main ingredients in our proofs are a novel randomized algorithm that generates asymmetric strictly balanced graphs as well as a new method to study symmetry groups of randomly perturbed graphs.

We prove that for each positive integer $n$, the Rips complexes of the $n$-dimensional integer lattice in the $d_1$ metric (i.e., the Manhattan metric, also called the natural word metric in the Cayley graph) are contractible at scales above $n^2(2n-1)^2$, with the bounds arising from the Jung's constants. We introduce a new concept of locally dominated vertices in a simplicial complex, upon which our proof strategy is based. This allows us to deduce the contractibility of the Rips complexes from a local geometric condition called local crushing. In the case of the integer lattices in dimension $n$ and a fixed scale $r$, this condition entails the comparison of finitely many distances to conclude that the corresponding Rips complex is contractible. In particular, we are able to verify that for $n=1,2,3$, the Rips complex of the $n$-dimensional integer lattice at scale greater or equal to $n$ is contractible. We conjecture that the same proof strategy can be used to extend this result to all dimensions $n$, Comment: 18 pages, 3 figures

The exploration of linear subspaces, particularly scattered subspaces, has garnered considerable attention across diverse mathematical disciplines in recent years, notably within finite geometries and coding theory. Scattered subspaces play a pivotal role in analyzing various geometric structures such as blocking sets, two-intersection sets, complete arcs, caps in affine and projective spaces over finite fields and rank metric codes. This paper introduces a new infinite family of $h$-subspaces, along with their associated MRD codes. Additionally, it addresses the task of determining the generalized weights of these codes. Notably, we demonstrate that these MRD codes exhibit some larger generalized weights compared to those previously identified.

Let $G_S$ be the graph obtained by attaching a self-loop at every vertex in $S \subseteq V(G)$ of a simple graph $G$ of order $n.$ In this paper, we explore several new results related to the line graph $L(G_S)$ of $G_S.$ Particularly, we show that every eigenvalue of $L(G_S)$ must be at least $-2,$ and relate the characteristic polynomial of the line graph $L(G)$ of $G$ with the characteristic polynomial of the line graph $L(\widehat{G})$ of a self-loop graph $\widehat{G}$, which is obtained by attaching a self-loop at each vertex of $G$. Then, we provide some new bounds for the eigenvalues and energy of $G_S.$ As one of the consequences, we obtain that the energy of a connected regular complete multipartite graph is not greater than the energy of the corresponding self-loop graph. Lastly, we establish a lower bound of the spectral radius in terms of the first Zagreb index $M_1(G)$ and the minimum degree $\delta(G),$ as well as proving two Nordhaus-Gaddum-type bounds for the spectral radius and the energy of $G_S,$ respectively., Comment: 19 pages. To appear in Bulletin of the Malaysian Mathematical Sciences Society

It is well known that the class of transversal matroids is not closed under contraction or duality. The complexity of deciding whether a minor or dual of a transversal matroid remains transversal is in $\Sigma_2$ and thus far there has been no improvement on this bound. We explore this issue, providing a polynomial time algorithm for determining whether a single element contraction of a transversal matroid remains transversal. If so, our algorithm also provides a transversal representation. We then develop the techniques used in search of a polynomial time algorithm for determining whether the dual of a transversal matroid remains transversal., Comment: 42 pages

Endothelial cells form the linchpin of vascular and lymphatic systems, creating intricate networks that are pivotal for angiogenesis, controlling vessel permeability, and maintaining tissue homeostasis. Despite their critical roles, there is no rigorous mathematical framework to represent the connectivity structure of endothelial networks. Here, we develop a pioneering mathematical formalism called $\pi$-graphs to model the multi-type junction connectivity of endothelial networks. We define $\pi$-graphs as abstract objects consisting of endothelial cells and their junction sets, and introduce the key notion of $\pi$-isomorphism that captures when two $\pi$-graphs have the same connectivity structure. We prove several propositions relating the $\pi$-graph representation to traditional graph-theoretic representations, showing that $\pi$-isomorphism implies isomorphism of the corresponding unnested endothelial graphs, but not vice versa. We also introduce a temporal dimension to the $\pi$-graph formalism and explore the evolution of topological invariants in spatial embeddings of $\pi$-graphs. Finally, we outline a topological framework to represent the spatial embedding of $\pi$-graphs into geometric spaces. The $\pi$-graph formalism provides a novel tool for quantitative analysis of endothelial network connectivity and its relation to function, with the potential to yield new insights into vascular physiology and pathophysiology., Comment: 14 pages, 9 figures

We study the lattice of submonoids of the uniform block permutation monoid containing the symmetric group (which is its group of units). We prove that this lattice is distributive under union and intersection by relating the submonoids containing the symmetric group to downsets in a new partial order on integer partitions. Furthermore, we show that the sizes of the $\mathscr{J}$-classes of the uniform block permutation monoid are sums of squares of dimensions of irreducible modules of the monoid algebra., Comment: 15 pages

In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on $n$ vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? We refer to such worst-case graphs as ``distance critical''. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions., Comment: 14 pages, 4 figures

We say a finite poset $P$ is a tree poset if its Hasse diagram is a tree. Let $k$ be the length of the largest chain contained in $P$. We show that when $P$ is a fixed tree poset, the number of $P$-free set systems in $2^{[n]}$ is $2^{(1+o(1))(k-1){n \choose \lfloor n/2\rfloor}}$. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.

In this paper we study $d$-dependent random graphs -- introduced by Brody and Sanchez -- which are the family of random graph distributions where each edge is present with probability $p$, and each edge is independent of all but at most $d$ other edges. For this random graph model, we analyze degree sequences, jumbledness, connectivity, and subgraph containment. Our results mirror those of the classical Erd\H{o}s--R\'enyi random graph, which are recovered by specializing our problem to $d=0$, although we show that in many regards our setting is appreciably more nuanced. We survey what is known for this model and conclude with a variety of open questions., Comment: 12 pages

For a graph $G$ and a hereditary property $\mathcal{P}$, let $\text{ex}(G,\mathcal{P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to $\mathcal{P}$. We prove that for every non-trivial hereditary property $\mathcal{P}$ such that $L \notin \mathcal{P}$ for some bipartite graph $L$ and for every fixed $p \in (0,1)$ we have \[\text{ex}(G(n,p),\mathcal{P}) \le n^{2-\varepsilon}\] with high probability, for some constant $\varepsilon = \varepsilon(\mathcal{P})>0$. This answers a question of Alon, Krivelevich and Samotij., Comment: 5 pages

The problem of counting polymer coverings on the rectangular lattices is investigated. In this model, a linear rigid polymer covers $k$ adjacent lattice sites such that no two polymers occupy a common site. Those unoccupied lattice sites are considered as monomers. We prove that for a given number of polymers ($k$-mers), the number of arrangements for the polymers on two-dimensional rectangular lattices satisfies simple recurrence relations. These recurrence relations are quite general and apply for arbitrary polymer length ($k$) and the width of the lattices ($n$). The well-studied monomer-dimer problem is a special case of the monomer-polymer model when $k=2$. It is known the enumeration of monomer-dimer configurations in planar lattices is #P-complete. The recurrence relations shown here have the potential for hints for the solution of long-standing problems in this class of computational complexity.

Abstract polytopes are combinatorial objects that generalise geometric objects such as convex polytopes, maps on surfaces and tilings of the space. Chiral polytopes are those abstract polytopes that admit full combinatorial rotational symmetry but do not admit reflections. In this paper we build chiral polytopes whose facets (maximal faces) are isomorphic to a prescribed regular cubic tessellation of the $n$-dimensional torus ($n \geq 2$). As a consequence, we prove that for every $d \geq 3$ there exist infinitely many chiral $d$-polytopes.

Cyclic polytopes have been studied since at least the early last century by Caratheodory and others.A generalization is a construction of a class of polytopes such that the polytopes have some of their properties.The best known example is the class of neighbourly polytopes. Cyclic polytopes have explicit facet structures, important properties and applications in different branches of mathematics. In the past few decades, generalizations of their combinatorial properties have yielded new classes of polytopes that also have explicit facet structures and useful applications. We present an overview of these generalizations along with some applications of the resultant polytopes, and some possible approaches to other generalizations., Comment: 10 pages

A linear equation $E$ is said to be sparse if there is $c>0$ so that every subset of $[n]$ of size $n^{1-c}$ contains a solution of $E$ in distinct integers. The problem of characterizing the sparse equations, first raised by Ruzsa in the 90's, is one of the most important open problems in additive combinatorics. We say that $E$ in $k$ variables is abundant if every subset of $[n]$ of size $\varepsilon n$ contains at least poly$(\varepsilon)\cdot n^{k-1}$ solutions of $E$. It is clear that every abundant $E$ is sparse, and Gir\~{a}o, Hurley, Illingworth and Michel asked if the converse implication also holds. In this note we show that this is the case for every $E$ in $4$ variables. We further discuss a generalization of this problem which applies to all linear equations.

We investigate the random bipartite optimal matching problem on a flat torus in two-dimensions, considering general strictly convex power costs of the distance. We extend the successful ansatz first introduced by Caracciolo et al. for the quadratic case, involving a linear Poisson equation, to a non-linear equation of $q$-Poisson type, allowing for a more comprehensive analysis of the optimal transport cost. Our results establish new asymptotic connections between the energy of the solution to the PDE and the optimal transport cost, providing insights on their asymptotic behavior.

We disprove the conjecture of Georgakopoulos and Papasoglu that a length space (or graph) with no $K$-fat $H$ minor is quasi-isometric to a graph with no $H$ minor. Our counterexample is furthermore not quasi-isometric to a graph with no 2-fat $H$ minor or a length space with no $H$ minor. On the other hand, we show that the following weakening holds: any graph with no $K$-fat $H$ minor is quasi-isometric to a graph with no $3$-fat $H$ minor., Comment: 14 pages, 5 figures

Paley graphs and Paley sum graphs are classical examples of quasi-random graphs. In this paper, we provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of studying various graphs arising from polynomials over finite fields such as Paley graphs, Paley sum graphs, and graphs coming from Diophantine tuples and their generalizations. We also provide new lower bounds on the clique number and independence number of general quasi-random graphs. In particular, we give a sufficient condition for the clique number of quasi-random graphs of $n$ vertices to be at least $(1-o(1)\log_{3.008}n$. Such a condition applies to many classical quasi-random graphs, including Paley graphs and Paley sum graphs, as well as some new Paley-like graphs we construct., Comment: 26 pages

We prove that the number of symmetric chain decompositions of the Boolean lattice $2^{[n]}$ is $$\left(\frac{n}{2e}+o(n)\right)^{2^n}.$$ Furthermore, the number of symmetric chain decompositions of the hypergrid $[t]^n$ is $$n^{(1-o_n(1))\cdot t^n}.$$, Comment: 7 pages

Kolmogorov complexity is often used as a convenient language for counting and/or probabilistic existence proofs. However, there are some applications where Kolmogorov complexity is used in a more subtle way. We provide one (somehow) surprising example where an existence of a winning strategy in a natural combinatorial game is proven (and no direct proof is known)., Comment: Prepared as an special session invited talk at CiE 2024

In this note we apply a spectral method to the graph of alternating bilinear forms. In this way, we obtain upper bounds on the size of an alternating rank-metric code for given values of the minimum rank distance. We computationally compare our results with Delsarte's linear programming bound, observing that they give the same value. For small values of the minimum rank distance, we are able to establish the equivalence of the two methods. The problem remains open for larger values.

The 2-distance coloring of a graph $G$ is equivalent to the proper coloring of its square graph $G^2$, it is a special distance labeling problem. DP-coloring (or "Correspondence coloring") was introduced by Dvo\v{r}\'ak and Postle in 2018, to answer a conjecture of list coloring proposed by Borodin. In recent years, many researches pay attention to the DP-coloring of planar graphs with some restriction in cycles. We study the DP-coloring of the square of subcubic graphs in terms of maximum average degree $\rm{mad}(G)$, and by the discharging method, we showed that: for a subcubic graph $G$, if $\rm{mad}(G)<9/4$, then $G^2$ is DP-5-colorable; if $\rm{mad}(G)<12/5$, then $G^2$ is DP-6-colorable. And the bound in the first result is sharp., Comment: 7 pages, 3 figures

Foata and Sch\"{u}tzenberger gave an expansion for the Eulerian polynomial $A_n(t)$ in terms of the basis $\{t^j(1+t)^{n-1-2j}\}$ for the space of polynomials $f(t)$ satisfying $f(t)=t^{n-1}f(1/t)$. We generalize this result in two ways. First, we provide an analogue for the graded representation of the symmetric group $\mathfrak{S}_n$ on the cohomology of the permutohedral variety. Then we give expansions $h$-polynomials of polytopes obtained by cutting permutohedra with hyperplanes orthogonal to simple roots in terms of the same basis., Comment: 13 pages

The main goal of this paper is to construct a new class of matroids coming from cluster algebras and investigate their properties., Comment: 7 pages, 2 figures

In this article, we present two new constructions for semifields of order $p^{2m}$. Together, the constructions unify and generalize around a dozen distinct semifield constructions, including both the oldest known construction by Dickson and the largest known construction in odd characteristic by Taniguchi. The constructions also provably yield many new semifields. We give precise conditions when the new semifields we find are equivalent and count precisely how many new inequivalent semifields we construct., Comment: 28 pages

Csikv\'{a}ri constructed a poset on trees to prove that several graph functions attain extreme values at the star and the path among the trees on a fixed number of vertices. Reiner and Smith proved that the Tutte polynomials $T(1,y)$ of cones over trees, which are the graphs obtained by attaching a cone vertex to a tree, have the described extreme behavior. They further conjectured that the result can be strengthened in terms of Csikv\'{a}ri's poset. We solve this conjecture affirmatively.

How can we probabilistically predict the winner in a ranked-choice election without all ballots being counted? In this study, we introduce a novel algorithm designed to predict outcomes in Instant Runoff Voting (IRV) elections. The algorithm takes as input a set of discrete probability distributions describing vote totals for each candidate ranking and calculates the probability that each candidate will win the election. In fact, we calculate all possible sequences of eliminations that might occur in the IRV rounds and assign a probability to each. The discrete probability distributions can be arbitrary and, in applications, could be measured empirically from pre-election polling data or from partial vote tallies of an in-progress election. The algorithm is effective for elections with a small number of candidates (five or fewer), with fast execution on typical consumer computers. The run-time is short enough for our method to be used for real-time election night modeling where new predictions are made continuously as more and more vote information becomes available. We demonstrate the algorithm in abstract examples, and also using real data from the 2022 Alaska state elections to simulate election-night predictions and also predictions of election recounts.

We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-difference degeneracy) at most $d$ if it admits an elimination order of its vertices where a vertex $u$ can be removed whenever it has a $d$-twin, i.e., another vertex $v$ such that at most $d$ vertices outside $\{u,v\}$ are neighbors of exactly one of $u, v$. The family of graph classes of bounded sd-degeneracy is a superset of that of graph classes of bounded degeneracy or of bounded flip-width, and more generally, of bounded symmetric difference. Unlike most graph parameters, sd-degeneracy is not hereditary: it may be strictly smaller on a graph than on some of its induced subgraphs. In particular, every $n$-vertex graph is an induced subgraph of some $O(n^2)$-vertex graph of sd-degeneracy 1. In spite of this and the breadth of classes of bounded sd-degeneracy, we devise $\tilde{O}(\sqrt n)$-bit adjacency labeling schemes for them, which are optimal up to the hidden polylogarithmic factor. This is attained on some even more general classes, consisting of graphs $G$ whose vertices bijectively map to the leaves of a tree $T$, where transversal edges and anti-edges added to $T$ define the edge set of $G$. We call such graph representations signed tree models as they extend the so-called tree models (or twin-decompositions) developed in the context of twin-width, by adding transversal anti-edges. While computing the degeneracy of an input graph can be done in linear time, we show that deciding whether its symmetric difference is at most 8 is co-NP-complete, and whether its sd-degeneracy is at most 1 is NP-complete., Comment: 21 pages, 7 figures

The ideal of the arc scheme of a double point or, equivalently, the differential ideal generated by the ideal of a double point is a primary ideal in an infinite-dimensional polynomial ring supported at the origin. This ideal has a rich combinatorial structure connecting it to singularity theory, partition identities, representation theory, and differential algebra. Macaulay inverse system is a powerful tool for studying the structure of primary ideals which describes an ideal in terms of certain linear differential operators. In the present paper, we show that the inverse system of the ideal of the arc scheme of a double point is precisely a vector space spanned by all the Wronskians of the variables and their formal derivatives. We then apply this characterization to extend our recent result on Poincar\'e-type series for such ideals.

We define a partial order $\mathcal{P}_n$ on permutations of any given size $n$, which is the image of a natural partial order on inversion sequences. We call this the ``middle order''. We demonstrate that the poset $\mathcal{P}_n$ refines the weak order on permutations and admits the Bruhat order as a refinement, justifying the terminology. These middle orders are distributive lattices and we establish some of their combinatorial properties, including characterization and enumeration of intervals and boolean intervals (in general, or of any given rank), and a combinatorial interpretation of their Euler characteristic. We further study the (not so well-behaved) restriction of this poset to involutions, obtaining a simple formula for the M\"obius function of principal order ideals there. Finally, we offer further directions of research, initiating the study of the canonical Heyting algebra associated with $\mathcal{P}_n$, and defining a parking function analogue of $\mathcal{P}_n$., Comment: 21 pages, 3 figures