In this paper, we establish an optimal $χ$-binding function for $(P_2\cup P_4,\text{ diamond})$-free graphs. We prove that for any graph $G$ in this class, $χ(G)\le 4$ when $ω(G)=2$, $χ(G)\le 6$ when $ω(G)=3$, and $χ(G)=ω(G)$ when $ω(G)\ge 4$, where $χ(G)$ and $ω(G)$ denote the chromatic number and clique number of $G$, respectively. This result extends the known chromatic bounds for $(P_2\cup P_3,\text{ diamond})$-free graphs by showing that $(P_2\cup P_4,\text{ diamond})$-free graphs admit the same $χ$-binding function. It also refines the chromatic bound obtained by Angeliya, Karthick and Huang [arXiv:2501.02543v3 [math.CO], 2025] for $(P_2\cup P_4,\text{ diamond})$-free graphs.
For a graph $G$, $χ(G)$ and $ω(G)$ respectively denote the chromatic number and clique number of $G$. In this paper, we show the following results: (i) If $G$ is a ($P_2+P_4$, $K_4-e$)-free graph with $ω(G)\geq 3$, then $χ(G)\leq \max\{6, ω(G)\}$, and the bound is tight for each $ω(G)\notin \{4,5\}$. (ii) If $G$ is a ($P_2+P_4$, $K_4-e$)-free graph with $ω(G)= 4$, then $χ(G)= 4$. These results extend the chromatic bounds known for the class of ($P_2+P_2$, $K_4-e$)-free graphs and for the class of ($P_2+P_3$, $K_4-e$)-free graphs, improve the bound of Chen and Zhang [arXiv:2412.14524 [math.CO], 2024] given for the class of ($P_2+P_4$, $K_4-e$)-free graphs, partially answer a question of Ju and the third author [Theor. Comp. Sci. 993 (2024) Article No.: 114465] on `near optimal colorable graphs', and a question of Schiermeyer (unpublished) on the chromatic bound for ($P_7$, $K_4-e$)-free graphs.
Emmanuel Chidiebere Duru, Michael Chimezie Anyanwu
Dengue and zika virus disease are flavivirus diseases that spread through bites of Aedes aegypti, a mosquito in the Aedes family. There have been emerging reports of co-infection of these two diseases in humans and Aedes aegypti, in the areas where the two diseases are prevalent. More so, the two diseases are known to manifest similar characteristic symptoms, which makes it possible for mis-diagnosis and wrong treatment. In this paper therefore, we model co-circulation and co-infection of dengue and zika virus disease in human and mosquito populations, with a system of non-linear ordinary differential equations. It is shown that the disease-free equilibrium of the model may not be globally asymptotically stable due to re-infection of infected humans and mosquitoes by the other disease. The impact of mis-diagnosis of the diseases is investigated which shows that mis-diagnosis would increase the spread of the diseases if the proportion of humans that are accurately diagnosed and treated is more than the rate of recovery of humans that are wrongly diagnosed and treated. Positive constants which give the rates at which the spread of one disease affects the spread of the other are obtained. Plots are given to visualize these important results.
The concept of the \textit{relative fractional packing number} between two graphs $G$ and $H$, initially introduced in arXiv:2307.06155 [math.CO], serves as an upper bound for the ratio of the zero-error Shannon capacity of these graphs. Defined as: \begin{equation*} \sup\limits_{W} \frac{α(G \boxtimes W)}{α(H \boxtimes W)} \end{equation*} where the supremum is computed over all arbitrary graphs and $\boxtimes$ denotes the strong product of graphs. This article delves into various critical theorems regarding the computation of this number. Specifically, we address its NP-hardness and the complexity of approximating it. Furthermore, we develop a conjecture for necessary and sufficient conditions for this number to be less than one. We also validate this conjecture for specific graph families. Additionally, we present miscellaneous concepts and introduce a generalized version of the independence number that gives insights that could significantly contribute to the study of the relative fractional packing number.
Characterizing sets of permutations whose associated quasisymmetric function is symmetric and Schur- positive is a long-standing problem in algebraic combinatorics. In this paper we present a general method to construct Schur-positive sets and multisets, based on geometric grid classes and the product operation. Our approach produces many new instances of Schur-positive sets, and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.
A fourientation of a graph G is a choice for each edge of the graph whether to orient that edge in either direction, leave it unoriented, or biorient it. We may naturally view fourientations as a mixture of subgraphs and graph orientations where unoriented and bioriented edges play the role of absent and present subgraph edges, respectively. Building on work of Backman and Hopkins (2015), we show that given a linear order and a reference orientation of the edge set, one can define activities for fourientations of G which allow for a new 12 variable expansion of the Tutte polynomial TG. Our formula specializes to both an orientation activities expansion of TG due to Las Vergnas (1984) and a generalized activities expansion of TG due to Gordon and Traldi (1990).
It is known that the number of minimal factorizations of the long cycle in the symmetric group into a product of k cycles of given lengths has a very simple formula: it is nk−1 where n is the rank of the underlying symmetric group and k is the number of factors. In particular, this is nn−2 for transposition factorizations. The goal of this work is to prove a multivariate generalization of this result. As a byproduct, we get a multivariate analog of Postnikov's hook length formula for trees, and a refined enumeration of final chains of noncrossing partitions.
The decision to retain was explored using semi-structured interviews with 14 students who previously completed a MATH-131 or MATH-137 course with a co-requisite support course enrollment. A follow-up survey was then developed and disseminated to 32 students to determine if interview responses were shared by other students. Responses were coded, categorized, and themed, and results indicated elements of the self-determination theory framework led to increased retention rates in co-requisite students. Triangulation was then achieved using a motivation inventory that was disseminated as a pre-test and then repeated at the end of the course as a post-test to both co-requisite (treatment) and non-co-requisite (control) students. Elements facilitating autonomy and competency within the co-requisite program were shown to significantly influence (at the 0.10 significance level) a student’s decision to maintain enrollment for one year following the successful completion of co-requisite courses (p = .004 and p = .079, respectively).<br>
'Tree-based' phylogenetic networks proposed by Francis and Steel have attracted much attention of theoretical biologists in the last few years. At the heart of the definitions of tree-based phylogenetic networks is the notion of 'support trees', about which there are numerous algorithmic problems that are important for evolutionary data analysis. Recently, Hayamizu (arXiv:1811.05849 [math.CO]) proved a structure theorem for tree-based phylogenetic networks and obtained linear-time and linear-delay algorithms for many basic problems on support trees, such as counting, optimisation, and enumeration. In the present paper, we consider the following fundamental problem in statistical data analysis: given a tree-based phylogenetic network $N$ whose arcs are associated with probability, create the top-$k$ support tree ranking for $N$ by their likelihood values. We provide a linear-delay (and hence optimal) algorithm for the problem and thus reveal the interesting property of tree-based phylogenetic networks that ranking top-$k$ support trees is as computationally easy as picking $k$ arbitrary support trees.
We show that the cyclohedron (Bott-Taubes polytope) $W_n$ arises as the dual of a Kantorovich-Rubinstein polytope $KR(ρ)$, where $ρ$ is a quasi-metric (asymmetric distance function) satisfying strict triangle inequality. From a broader perspective, this phenomenon illustrates the relationship between a nestohedron $Δ_{\mathcal{\widehat{F}}}$ (associated to a building set $\mathcal{\widehat{F}}$) and its non-simple deformation $Δ_{\mathcal{F}}$, where $\mathcal{F}$ is an `irredundant' or `tight basis' of $\mathcal{\widehat{F}}$. Among the consequences are a new proof of a recent result of Gordon and Petrov (arXiv:1608.06848 [math.CO]) about $f$-vectors of generic Kantorovich-Rubinstein polytopes and an extension of a theorem of Gelfand, Graev, and Postnikov, about triangulations of the type A, positive root polytopes.
We prove two sharp sufficient conditions for hamiltonian cycles in balanced bipartite directed graph. Let $D$ be a strongly connected balanced bipartite directed graph of order $2a$. Let $x,y$ be distinct vertices in $D$. $\{x,y\}$ dominates a vertex $z$ if $x\rightarrow z$ and $y\rightarrow z$; in this case, we call the pair $\{x,y\}$ dominating. (i) {\it If $a\geq 4$ and $max \{d(x), d(y)\}\geq 2a-1$ for every dominating pair of vertices $\{x,y\}$, then either $D$ is hamiltonian or $D$ is isomorphic to one exceptional digraph of order eight.} (ii) {\it If $a\geq 5$ and $d(x)+d(y)\geq 4a-3$ for every dominating pair of vertices $\{x,y\}$, then $D$ is hamiltonian.} The first result improves a theorem of R. Wang (arXiv:1506.07949 [math.CO]), the second result, in particular, establishes a conjecture due to Bang-Jensen, Gutin and Li (J. Graph Theory , 22(2), 1996) for strongly connected balanced bipartite digraphs of order at least ten.
We define an action of the $0$-Hecke algebra of type A on the Stanley-Reisner ring of the Boolean algebra. By studying this action we obtain a family of multivariate noncommutative symmetric functions, which specialize to the noncommutative Hall-Littlewood symmetric functions and their $(q,t)$-analogues introduced by Bergeron and Zabrocki. We also obtain multivariate quasisymmetric function identities, which specialize to a result of Garsia and Gessel on the generating function of the joint distribution of five permutation statistics.
The set of weights of a finite-dimensional representation of a reductive Lie algebra has a natural poset structure ("weight poset"). Studying certain combinatorial problems related to antichains in weight posets, we realised that the best setting is provided by the representations associated with $\mathbb Z$-gradings of simple Lie algebras (arXiv: math.CO 1411.7683). If $\mathfrak g$ is a simple Lie algebra, then a $\mathbb Z$-grading of $\mathfrak g$ induces a $\mathbb Z$-grading of the corresponding root system $Δ$. In this article, we elaborate on a general theory of lower ideals (or antichains) in the corresponding weight posets $Δ(1)$. In particular, we provide a bijection between the lower ideals in $Δ(1)$ and certain elements of the Weyl group of $\mathfrak g$. An inspiring observation is that, to a great extent, the theory of lower ideals in $Δ(1)$ is similar to the theory of upper (= ad-nilpotent) ideals in the whole poset of positive roots $Δ^+$.
Macdonald processes are certain probability measures on two-dimensional arrays of interlacing particles introduced by Borodin and Corwin (arXiv:1111.4408 [math.PR]). They are defined in terms of nonnegative specializations of the Macdonald symmetric functions and depend on two parameters (q,t), where 0<= q, t < 1. Our main result is a classification of continuous time, nearest neighbor Markov dynamics on the space of interlacing arrays that act nicely on Macdonald processes. The classification unites known examples of such dynamics and also yields many new ones. When t = 0, one dynamics leads to a new integrable interacting particle system on the one-dimensional lattice, which is a q-deformation of the PushTASEP (= long-range TASEP). When q = t, the Macdonald processes become the Schur processes of Okounkov and Reshetikhin (arXiv:math/0107056 [math.CO]). In this degeneration, we discover new Robinson--Schensted-type correspondences between words and pairs of Young tableaux that govern some of our dynamics.
Michael Drmota, Bernhard Gittenberger, Johannes F. Morgenbesser
In this paper infinite systems of functional equations in finitely or infinitely many random variables arising in combinatorial enumeration problems are studied. We prove sufficient conditions under which the combinatorial random variables encoded in the generating function of the system tend to a finite or infinite dimensional limiting distribution.
We give an elementary proof of a formula expressing the rotation number of a cyclic unimodular sequence of lattice vectors in terms of arithmetically defined local quantities. The formula has been originally derived by A. Higashitani and M. Masuda (arXiv:1204.0088v2 [math.CO]) with the aid of the Riemann-Roch formula applied in the context of toric topology. They also demonstrated that a generalized versions of the "Twelve-point theorem" and a generalized Pick's formula are among the consequences or relatives of their result. Our approach emphasizes the role of 'discrete curvature invariants' μ(a,b,c), where {a,b} and {b,c} are bases of the lattice Z^2, as fundamental discrete invariants of 'modular lattice geometry'.
Words $a_1 a_2 \ldots a_n$ with independent letters $a_k$ taken from the set of natural numbers, and a weight (probability) attached via the geometric distribution $pq^{i-1}(p+q=1)$ are considered. A consecutive record (motivated by the analysis of a skip list structure) can only advance from $k$ to $k+1$, thus ignoring perhaps some larger (=superior) values. We investigate the number of these rejected superior values. Further, we study the probability that there is a single consecutive maximum and show that (apart from fluctuations) it tends to a constant.
Studying cellular automata with methods from communication complexity appears to be a promising approach. In the past, interesting connections between communication complexity and intrinsic universality in cellular automata were shown. One of the last extensions of this theory was its generalization to various "communication problems'', or "questions'' one might ask about the dynamics of cellular automata. In this article, we aim at structuring these problems, and find what makes them interesting for the study of intrinsic universality and quasi-orders induced by simulation relations.
A characterization of $\mathbb{Z} _t \times \mathbb{Z}_2^2$-cocyclic Hadamard matrices is described, depending on the notions of {\em distributions}, {\em ingredients} and {\em recipes}. In particular, these notions lead to the establishment of some bounds on the number and distribution of 2-coboundaries over $\mathbb{Z}_t \times \mathbb{Z} _2^2$ to use and the way in which they have to be combined in order to obtain a $\mathbb{Z} _t \times \mathbb{Z}_2^2$-cocyclic Hadamard matrix. Exhaustive searches have been performed, so that the table in p. 132 in [4] is corrected and completed. Furthermore, we identify four different operations on the set of coboundaries defining $\mathbb{Z} _t \times \mathbb{Z}_2^2$-cocyclic matrices, which preserve orthogonality. We split the set of Hadamard matrices into disjoint orbits, define representatives for them and take advantage of this fact to compute them in an easier way than the usual purely exhaustive way, in terms of {\em diagrams}. Let ${\cal H}$ be the set of cocyclic Hadamard matrices over $\mathbb{Z}_t \times \mathbb{Z}_2^2$ having a symmetric diagram. We also prove that the set of Williamson type matrices is a subset of ${\cal H}$ of size $\frac{|{\cal H}|}{t}$.
We aim to generalize a theorem on the number of rooted spanning forests of a highly symmetric graph to the case of asymmetric graphs. We show that this can be achieved by means of an identity between the minor determinants of a Laplace matrix, for which we provide two different (combinatorial as well as algebraic) proofs in the simplest case. Furthermore, we discuss the connections to electrical networks and the enumeration of spanning trees in sequences of self-similar graphs.