Search

We present novel results related to isomorphic resonance graphs of 2-connected outerplane bipartite graphs. As the main result, we provide a structure characterization for 2-connected outerplane bipartite graphs with isomorphic resonance graphs. Moreover, two additional characterizations are expressed in terms of resonance digraphs and via local structures of inner duals of 2-connected outerplane bipartite graphs, respectively.

We calculate the volume of the tropical Prym variety of a harmonic double cover of metric graphs having non-trivial dilation. We show that the tropical Prym variety behaves discontinuously under deformations of the double cover that change the number of connected components of the dilation subgraph., Comment: 17 pages, 3 figures

Concerning the recent notion of circular chromatic number of signed graphs, for each given integer $k$ we introduce two signed bipartite graphs, each on $2k^2-k+1$ vertices, having shortest negative cycle of length $2k$, and the circular chromatic number 4. Each of the construction can be viewed as a bipartite analogue of the generalized Mycielski graphs on odd cycles, $M_{\ell}(C_{2k+1})$. In the course of proving our result, we also obtain a simple proof of the fact that $M_{\ell}(C_{2k+1})$ and some similar quadrangulations of the projective plane have circular chromatic number 4. These proofs have the advantage that they illuminate, in an elementary manner, the strong relation between algebraic topology and graph coloring problems., Comment: 16 pages, 11 figures

In 1933, Karol Borsuk asked whether each bounded set in the $n$-dimensional Euclidean space can be divided into $n$+1 parts of smaller diameter. Because it would not make sense otherwise, one usually assumes that he just forgot to require that the whole set contains at least two points. The hypothesis that the answer to that question is positive became famous under the name \emph{Borsuk's conjecture}. Counterexamples are known for any $n\ge 64$, since 2013. Let $\Lambda$ the (original, unscaled) Leech lattice, a now very well-known infinite discrete vector set in the 24-dimensional Euclidean space. The smallest norm of nonzero vectors in $\Lambda$ is $\sqrt{32}$. Let $M$ the set of the 196560 vectors in $\Lambda$ having this norm. For each $x \in M$, $-x$ is in $M$. Let $H$ the set of all subsets of $M$ that for each $x$ in $M$ contain either $x$ or $-x$. Each element of $H$ has the same diameter $d = \sqrt{96}$. For dimensions $n, Comment: 5 pages; v2: progress for n=22, correction in (2) in section 3

We consider $q$-binomial coefficients built from the $q$-rational and $q$-real numbers defined by Morier-Genoud and Ovsienko in terms of continued fractions. We establish versions of both the $q$-Pascal identity and the $q$-binomial theorem in this setting. These results are then used to find more identities satisfied by the $q$-analogues of Morier-Genoud and Ovsienko, including a Chu--Vandermonde identity and $q$-Gamma function identities.

The derived graph of a voltage graph consisting of a single vertex and two loops of different voltages is a circulant graph with two generators. We characterize the automorphism groups of connected, two-generator circulant graphs, and give their determining and distinguishing number, and when relevant, their cost of 2-distinguishing. We do the same for the subdivisions of connected, two-generator circulant graphs obtained by replacing one loop in the voltage graph with a directed cycle.

We generalize the perfectly clustering words of Simpson and Puglisi and relate them to band bricks over certain gentle algebras. This allows us to prove a generalization of a conjecture by the second author on perfectly clustering words., Comment: 37 pages

We investigate the rationality of Weil sums of binomials of the form $W^{K,s}_u=\sum_{x \in K} \psi(x^s - u x)$, where $K$ is a finite field whose canonical additive character is $\psi$, and where $u$ is an element of $K^{\times}$ and $s$ is a positive integer relatively prime to $|K^\times|$, so that $x \mapsto x^s$ is a permutation of $K$. The Weil spectrum for $K$ and $s$, which is the family of values $W^{K,s}_u$ as $u$ runs through $K^\times$, is of interest in arithmetic geometry and in several information-theoretic applications. The Weil spectrum always contains at least three distinct values if $s$ is nondegenerate (i.e., if $s$ is not a power of $p$ modulo $|K^\times|$, where $p$ is the characteristic of $K$). It is already known that if the Weil spectrum contains precisely three distinct values, then they must all be rational integers. We show that if the Weil spectrum contains precisely four distinct values, then they must all be rational integers, with the sole exception of the case where $|K|=5$ and $s \equiv 3 \pmod{4}$., Comment: 32 pages

The recent interest in $q$-Stirling numbers of the second kind in type B prompted us to give a type B analogue of a classical identity connecting the $q$-Stirling numbers of the second kind and Carlitz's major $q$-Eulerian numbers, which turns out to be a $q$-analogue of an identity due to Bagno, Biagioli and Garber. We provide a combinatorial proof of this identity and an analytical proof of a more general identity for colored permutations. In addition, we prove some $q$-identities about the $q$-Stirling numbers of the second kind in types A, B and D., Comment: 24 pages

The paper surveys recent progress in understanding geometric, topological and combinatorial properties of large simplicial complexes, focusing mainly on ampleness, connectivity and universality. In the first part of the paper we concentrate on $r$-ample simplicial complexes which are high dimensional analogues of the $r$-e.c. graphs introduced originally by Erd\H os and R\'eniy. The class of $r$-ample complexes is useful for applications since these complexes allow extensions of subcomplexes of certain type in all possible ways; besides, $r$-ample complexes exhibit remarkable robustness properties. We discuss results about the existence of $r$-ample complexes and describe their probabilistic and deterministic constructions. The properties of random simplicial complexes in medial regime are important for this discussion since these complexes are ample, in certain range. We prove that the topological complexity of a random simplicial complex in the medial regime satisfies ${\sf TC}(X)\le 4$, with probability tending to $1$ as $n\to\infty$. There exists a unique (up to isomorphism) $\infty$-ample complex on countable set of vertexes (the Rado complex), and the second part of the paper surveys the results about universality, homogeneity, indestructibility and other important properties of this complex. The Appendix written by J.A. Barmak discusses connectivity of conic and ample complexes., Comment: The Appendix was written by J.A. Barmak. arXiv admin note: text overlap with arXiv:2012.01483

We use Menger's Theorem and K\"onig's Line Colouring Theorem to show that in any tripartite graph with two complete (bipartite) sides the maximum number of pairwise edge-disjoint triangles equals the minimum number of edges that meet all triangles. This generalizes the corresponding result for complete tripartite graphs given by Lakshmanan, et al., Comment: 8 pages, 4 figures

In this paper, we study the value distributions of perfect nonlinear functions, i.e., we investigate the sizes of image and preimage sets. Using purely combinatorial tools, we develop a framework that deals with perfect nonlinear functions in the most general setting, generalizing several results that were achieved under specific constraints. For the particularly interesting elementary abelian case, we derive several new strong conditions and classification results on the value distributions. Moreover, we show that most of the classical constructions of perfect nonlinear functions have very specific value distributions, in the sense that they are almost balanced. Consequently, we completely determine the possible value distributions of vectorial Boolean bent functions with output dimension at most 4. Finally, using the discrete Fourier transform, we show that in some cases value distributions can be used to determine whether a given function is perfect nonlinear, or to decide whether given perfect nonlinear functions are equivalent., Comment: 28 pages

Normal complexes are orthogonal truncations of polyhedral fans. In this paper, we develop the study of mixed volumes for normal complexes. Our main result is a sufficiency condition that ensures when the mixed volumes of normal complexes associated to a given fan satisfy the Alexandrov-Fenchel inequalities. By specializing to Bergman fans of matroids, we give a new proof of the Heron-Rota-Welsh Conjecture as a consequence of the Alexandrov-Fenchel inequalities for normal complexes., Comment: 37 pages, 17 images, comments welcome

We prove the addition-deletion theorems for the Solomon-Terao polynomials, which have two important specializations. Namely, one is to the characteristic polynomials of hyperplane arangements, and the other to the Poincar\`{e} polynomials of the regular nilpotent Hessenberg varieties. One of the main tools to show them is the free surjection theorem which confirms the right exactness of several important exact sequences among logarithmic modules. Moreover, we introduce a generalized polynomial $B$-theory to the higher order logarithmic modules, whose origin was due to Terao., Comment: 22 pages

Consider the restricted Hanoi graphs which correspond to the variants of the famous Tower of Hanoi problem with multiple pegs where moves of the discs are restricted throughout the arcs of a movement digraph whose vertices represent the pegs of the puzzle and an arc from vertex $p$ to vertex $q$ exists if and only if moves from peg $p$ to peg $q$ are allowed. In this paper, we gave some notes on how to construct the restricted Hanoi graphs as well as some combinatorial results on the number of arcs in these graphs., Comment: 8 pages, 2 figures

Recently, new combinatorial structures called disjoint partial difference families (DPDFs) and external partial difference families (EPDFs) were introduced, which simultaneously generalize partial difference sets, disjoint difference families and external difference families, and have applications in information security. So far, all known construction methods have used cyclotomy in finite fields. We present the first non-cyclotomic infinite families of DPDFs which are also EPDFs, in structures other than finite fields (in particular cyclic groups and non-abelian groups). As well as direct constructions, we present an approach to constructing DPDFs/EPDFs using relative difference sets (RDSs); as part of this, we demonstrate how the well-known RDS result of Bose extends to a very natural construction for DPDFs and EPDFs.

We continue our study of the density of the odd values of eta-quotients, here focusing on the $m$-regular partition functions $b_m$ for $m$ even. Based on extensive computational evidence, we propose an elegant conjecture which, in particular, completely classifies such densities: Let $m = 2^j m_0$ with $m_0$ odd. If $2^j < m_0$, then the odd density of $b_m$ is $1/2$; moreover, such density is equal to $1/2$ on every (nonconstant) subprogression $An+B$. If $2^j > m_0$, then $b_m$, which is already known to have density zero, is identically even on infinitely many non-nested subprogressions. This and all other conjectures of this paper are consistent with our ''master conjecture'' on eta-quotients presented in the previous work. In general, our results on $b_m$ for $m$ even determine behaviors considerably different from the case of $m$ odd. Also interesting, it frequently happens that on subprogressions $An+B$, $b_m$ matches the parity of the multipartition functions $p_t$, for certain values of $t$. We make a suitable use of Ramanujan-Kolberg identities to deduce a large class of such results; as an example, $b_{28}(49n+12) \equiv p_3(7n+2) \pmod{2}$. Additional consequences are several ''almost always congruences'' for various $b_m$, as well as new parity results specifically for $b_{11}$. We wrap up our work with a much simpler proof of the main result of a recent paper by Cherubini-Mercuri, which fully characterized the parity of $b_8$., Minor revisions. To appear in the J. of Number Theory

The box-ball system (BBS), which was introduced by Takahashi and Satsuma in 1990, is a soliton cellular automaton. Its dynamics can be linearized by a few methods, among which the best known is the Kerov-Kirillov-Reschetikhin (KKR) bijection using rigged partitions. Recently a new linearization method in terms of "slot configurations" was introduced by Ferrari-Nguyen-Rolla-Wang, but its relations to existing ones have not been clarified. In this paper we investigate this issue and clarify the relation between the two linearizations. For this we introduce a novel way of describing the BBS dynamics using a carrier with seat numbers. We show that the seat number configuration also linearizes the BBS and reveals explicit relations between the KKR bijection and the slot configuration. In addition, by using these explicit relations, we also show that even in case of finite carrier capacity the BBS can be linearized via the slot configuration., Comment: 33 pages, 12 figures

Absolute combinatorial game theory was recently developed as a unifying tool for constructive/local game comparison (Larsson et al. 2018). The theory concerns {\em parental universes} of combinatorial games; standard closure properties are satisfied and each pair of non-empty sets of forms of the universe makes a form of the universe. Here we prove that there is an infinite number of absolute mis\`ere universes, by recursively expanding the dicot mis\`ere universe and the dead-ending universe. On the other hand, we prove that normal-play has exactly two absolute universes, namely the full space, and the universe of all-small games., Comment: 19 pages

Using the fact that the quasi depth is an upper bound for the Stanley depth of a quotient of squarefree monomial ideals, we prove several combinatorial inequalities which involve the coefficients of $f(t)=(1+t+\cdots+t^{m-1})^n$., Comment: 11 pages. arXiv admin note: text overlap with arXiv:2306.11015, arXiv:2306.09450

This paper gives some theory and efficient design of binary block systematic codes capable of controlling the deletions of the symbol ``$0$'' (referred to as $0$-deletions) and/or the insertions of the symbol ``$0$'' (referred to as $0$-insertions). The problem of controlling $0$-deletions and/or $0$-insertions (referred to as $0$-errors) is known to be equivalent to the efficient design of $L_{1}$ metric asymmetric error control codes over the natural alphabet, $\mathbb{N}$. So, $t$ $0$-insertion correcting codes can actually correct $t$ $0$-errors, detect $(t+1)$ $0$-errors and, simultaneously, detect all occurrences of only $0$-deletions or only $0$-insertions in every received word (briefly, they are $t$-Symmetric $0$-Error Correcting/$(t+1)$-Symmetric $0$-Error Detecting/All Unidirectional $0$-Error Detecting ($t$-Sy$0$EC/$(t+1)$-Sy$0$ED/AU$0$ED) codes). From the relations with the $L_{1}$ distance, optimal systematic code designs are given. In general, for all $t,k\in\mathbb{N}$, a recursive method is presented to encode $k$ information bits into efficient systematic $t$-Sy$0$EC/$(t+1)$-Sy$0$ED/AU$0$ED codes of length $$ n\leq k+t\log_{2}k+o(t\log n) $$ as $n\in\mathbb{N}$ increases. Decoding can be efficiently performed by algebraic means using the Extended Euclidean Algorithm (EEA).

We show that for any integer $k\ge 1$ there exists an integer $t_0(k)$ such that for integers $t, k_1, \ldots, k_{t+1}, n$ with $t>t_0(k)$, $\max\{k_1, \ldots, k_{t+1}\}\le k$, and $n > 2k(t+1)$, the following holds: If $F_i \subseteq {[n]\choose k_i}$ and $|F_i|> {n\choose k_i}-{n-t\choose k_i} - {n-t-k \choose k_i-1} + 1$ for all $i \in [t+1]$, then either $\{F_1,\ldots, F_{t+1}\}$ admits a rainbow matching of size $t+1$ or there exists $W\in {[n]\choose t}$ such that $W$ is a vertex cover of $F_i$ for all $i\in [t+1]$. This may be viewed as a rainbow non-uniform extension of the classical Hilton-Milner theorem. We also show that the same holds for every $t$ and $n > 2k^3t$, generalizing a recent stability result of Frankl and Kupavskii on matchings to rainbow matchings., arXiv admin note: text overlap with arXiv:2004.12561

A state model for Kauffman polynomial of Dubrovnik-version is given. Based on the state model, the Gauss diagram formulae for Vassiliev invariants are given from the coefficients of Kauffman polynomial following the method of Chmutov and Polyak. Some arrow diagram identities are given to simplify the Gauss diagram formulae of order 3, which give Polyak-Viro and Chmutov-Polyak formulae for the Vassiliev invariant of order 3. The models of Kauffman polynomial and HOMFLY-PT polynomial give different Gauss diagram expressions when specializing to Jones poynomial., Comment: 23 pages

Let $G$ be a graph with vertex set $V$. A set $S \subseteq V$ is a \emph{strong resolving set} of $G$ if, for distinct $x,y\in V$, there exists $z\in S$ such that either $x$ lies on a $y-z$ geodesic or $y$ lies on an $x-z$ geodesic in $G$. In this paper, we study maker-breaker strong resolving game (MBSRG) played on a graph by two players, Maker and Breaker, where the two players alternately select a vertex of $G$ not yet chosen. Maker wins if he is able to choose vertices that form a strong resolving set of $G$ and Breaker wins if she is able to prevent Maker from winning in the course of MBSRG. We denote by $O_{\rm SR}(G)$ the outcome of MBSRG played on $G$. We obtain some general results on MBSRG and examine the relation between $O_{\rm SR}(G)$ and $O_{\rm R}(G)$, where $O_{\rm R}(G)$ denotes the outcome of the maker-breaker resolving game of $G$. We determine the outcome of MBSRG played on some graph classes, including corona product graphs and Cartesian product graphs., Comment: 12 pages, 0 figures

We study three combinatorial models for the lower-triangular matrix with entries $t_{n,k} = \binom{n}{k} n^{n-k}$: two involving rooted trees on the vertex set $[n+1]$, and one involving partial functional digraphs on the vertex set $[n]$. We show that this matrix is totally positive and that the sequence of its row-generating polynomials is coefficientwise Hankel-totally positive. We then generalize to polynomials $t_{n,k}(y,z)$ that count improper and proper edges, and further to polynomials $t_{n,k}(y,\mathbf{\phi})$ in infinitely many indeterminates that give a weight $y$ to each improper edge and a weight $m! \, \phi_m$ for each vertex with $m$ proper children. We show that if the weight sequence $\mathbf{\phi}$ is Toeplitz-totally positive, then the two foregoing total-positivity results continue to hold. Our proofs use production matrices and exponential Riordan arrays., Comment: LaTeX2e, 75 pages, includes 16 figures. arXiv admin note: substantial text overlap with arXiv:2105.05583

We introduce the Ungarian Markov chain ${\bf U}_L$ associated to a finite lattice $L$. The states of this Markov chain are the elements of $L$. When the chain is in a state $x\in L$, it transitions to the meet of $\{x\}\cup T$, where $T$ is a random subset of the set of elements covered by $x$. We focus on estimating $\mathcal E(L)$, the expected number of steps of ${\bf U}_L$ needed to get from the top element of $L$ to the bottom element of $L$. Using direct combinatorial arguments, we provide asymptotic estimates when $L$ is the weak order on the symmetric group $S_n$ and when $L$ is the $n$-th Tamari lattice. When $L$ is distributive, the Markov chain ${\bf U}_L$ is equivalent to an instance of the well-studied random process known as last-passage percolation with geometric weights. One of our main results states that if $L$ is a trim lattice, then $\mathcal E(L)\leq\mathcal E(\text{spine}(L))$, where $\text{spine}(L)$ is a specific distributive sublattice of $L$ called the spine of $L$. Combining this lattice-theoretic theorem with known results about last-passage percolation yields a powerful method for proving upper bounds for $\mathcal E(L)$ when $L$ is trim. We apply this method to obtain uniform asymptotic upper bounds for the expected number of steps in the Ungarian Markov chains of Cambrian lattices of classical types and the Ungarian Markov chains of $\nu$-Tamari lattices., Comment: 36 pages, 9 figures

The {\em topological symmetry group} of an embedding $\Gamma$ of an abstract graph $\gamma$ in $S^3$ is the group of automorphisms of $\gamma$ which can be realized by homeomorphisms of the pair $(S^3, \Gamma)$. These groups are motivated by questions about the symmetries of molecules in space. The Petersen family of graphs is an important family of graphs for many problems in low dimensional topology, so it is desirable to understand the possible groups of symmetries of their embeddings in space. In this paper, we find all the groups which can be realized as topological symmetry groups for each of the graphs in the Petersen Family. Along the way, we also complete the classification of the realizable topological symmetry groups for $K_{3,3}$., Comment: 20 pages, many figures. v2 makes various small changes, and adds a conclusion section. This is the version accepted in Symmetry

For a given graph $F$, the $F$-saturation number of a graph $G$, denoted by $ {sat}(G, F)$, is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. In 2017, Kor\'andi and Sudakov determined $ {sat}({G}(n, p), K_r)$ asymptotically, where ${G}(n, p) $ denotes the Erd\H{o}s-R\'enyi random graph and $ K_r$ is the complete graph on $r$ vertices. In this paper, among other results, we present an asymptotic upper bound on ${sat}({G}(n, p), F)$ for any bipartite graph $F$ and also an asymptotic lower bound on ${sat}({G}(n, p), F)$ for any complete bipartite graph $F$.

When G denotes a graph, the unlabeled subgraph obtained by deleting a vertex from G is called a card of G and the collection of all cards of G is the deck of G. A graph having the same deck as G is called a hypomorph of G. A graph is called reconstructible if it is isomorphic to all its hypomorphs. Reconstruction Conjecture claims that all graphs are reconstructible and it is open. A representation of a hypomorph of G in terms of two of its cards, called pasting, is introduced. Isomorphic pastings of two cards is defined. In the case of a digraph, a card with which the degree triple of the deleted vertex is also given is called a degree associated card or dacard. Dadeck, dareconstructible digraphs, dapastings and isomorphic dapastings based on dacards are defined analogously. DARC claims that all digraphs are dareconstructible and it is also open. Results: Two hypomorphs G and H of a graph are isomorphic if and only if a pair of cards in their common deck is pasted isomorphically in both G and H. Either every pair of cards in their common deck is pasted isomorphically in both G and H, or no pair of cards is pasted isomorphically in both G and H. Results analogous to the above hold for dapastings in dahypomorphs of a digraph. Some results on pastings are proved and two graph parameters are reconstructed. The neighborhood degree quintuple of a vertex and a new family of digraphs are dareconstructible. New approaches for proving the reconstruction conjecture and DARC by the method of contradiction arise., Comment: 20 pages, 8 figures

The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from the final resolution; there is a lower bound of 7 coming from a construction by Kr\'al' and Lamaison [arXiv, September 2022], and an upper bound of 8 by Hlin\v{e}n\'y and Jedelsk\'y [arXiv, October 2022]. The upper bound (currently best) of 8, however, is rather complicated and involved. We give a short and simple self-contained proof that the twin-width of planar graphs is at most 11., Comment: to appear in Eurocomb'23

We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Set, are polynomial-time solvable in the class of $P_6$-free graphs. This generalizes the work of Grzesik, Klimo\v{s}ov\'{a}, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in $P_6$-free graphs~[SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rz\k{a}\.zewski, and Seymour on problems in $P_5$-free graphs~[SODA~2021]. The key step is a new generalization of the framework of potential maximal cliques. We show that instead of listing a large family of potential maximal cliques, it is sufficient to only list their carvers: vertex sets that contain the same vertices from the sought solution and have similar separation properties.

We give an exponential improvement to the diagonal van der Waerden numbers for $r\ge 5$ colors., Comment: 11 pages, comments welcome!

Free cumulants are multilinear functionals defined in terms of the moment functional with the use of the family of lattices of noncrossing partitions. In the univariate case, they can be identified with the coefficients of the Voiculescu transform of the moment functional which plays a role similar to that of the logarithm of the Fourier transform. The associated linearization property is connected with free independence. In turn, the family of much smaller lattices of interval partitions is used to define Boolean cumulants connected with Boolean independence. In order to bridge the gap between these two families of lattices and the associated cumulants we introduce and study the family of lattices of noncrossing partitions adapted to Motzkin paths and define the associated operator-valued `Motzkin cumulants'. We prove the corresponding M\"{o}bius inversion formula which plays the role of a lattice refinement of the formula expressing free cumulants in terms of Boolean cumulants. We apply this concept to free probability and obtain the additive decomposition of free cumulants in terms of scalar-valued counterparts of Motzkin cumulants., Comment: 55 pages, 4 figures

Submodular setfunctions play an important role in potential theory, and a perhaps even more important role in combinatorial optimization. The analytic line of research goes back to the work of Choquet; the combinatorial, to the work of Rado and Edmonds. The two research lines have not had much interaction though. Recently, with the development of graph limit theory, the question of a limit theory for matroids has been asked by several people; such a theory will, most likely, involve submodular setfunctions both on finite and infinite sets. The goal of this working paper is to describe several connections between the analytic and combinatorial theory, to show parallels between them, and to propose problems arising by trying the generalize the rich theory of submodular setfunctions on finite sets to the analytic setting. It is aimed more to combinatorialists, and it spends more time on developing the analytic theory, often referring to results in combinatorial optimization by name or sketch, Comment: 49 pages

We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from a color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, then we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids.

We introduce the spectral influence and spectral cyclicality based on the largest eigenvalue of a graph adjacency matrix, two novel concepts of centrality capturing diffusion and interdependence from a local and a global point of view respectively. We define a new clustering algorithm to distinguish communities with high cyclicality and interdependence, allowing overlapping, and we conclude our study with an application to the input-output analysis in the case of the Moroccan economy.

Given a digraph $D=(V,A)$ on $n$ vertices and a vertex $v\in V$, the cycle-degree of $v$ is the minimum size of a set $S \subseteq V(D) \setminus \{v\}$ intersecting every directed cycle of $D$ containing $v$. From this definition of cycle-degree, we define the $c$-degeneracy (or cycle-degeneracy) of $D$, which we denote by $\delta^*_c(D)$. It appears to be a nice generalisation of the undirected degeneracy. In this work, using this new definition of cycle-degeneracy, we extend several evidences for Cereceda's conjecture to digraphs. The $k$-dicolouring graph of $D$, denoted by $\mathcal{D}_k(D)$, is the undirected graph whose vertices are the $k$-dicolourings of $D$ and in which two $k$-dicolourings are adjacent if they differ on the colour of exactly one vertex. We show that $\mathcal{D}_k(D)$ has diameter at most $O_{\delta^*_c(D)}(n^{\delta^*_c(D) + 1})$ (respectively $O(n^2)$ and $(\delta^*_c(D)+1)$) when $k$ is at least $\delta^*_c(D)+2$ (respectively $\frac{3}{2}(\delta^*_c(D)+1)$ and $2(\delta^*_c(D)+1)$). This improves known results on digraph redicolouring (Bousquet et al.). Next, we extend a result due to Feghali to digraphs, showing that $\mathcal{D}_{d+1}(D)$ has diameter at most $O_{d,\epsilon}(n(\log n)^{d-1})$ when $D$ has maximum average cycle-degree at most $d-\epsilon$. We then show that two proofs of Bonamy and Bousquet for undirected graphs can be extended to digraphs. The first one uses the digrundy number of a digraph and the second one uses the $\mathscr{D}$-width. Finally, we give a general theorem which makes a connection between the recolourability of a digraph $D$ and the recolourability of its underlying graph $UG(D)$. This result directly extends a number of results on planar graph recolouring to planar digraph redicolouring., Comment: 24 pages, 2 figures

Building up on our previous works regarding $q$-deformed $P$-partitions, we introduce a new family of subalgebras for the ring of quasisymmetric functions. Each of these subalgebras admits as a basis a $q$-analogue to Gessel's fundamental quasisymmetric functions where $q$ is equal to a complex root of unity. Interestingly, the basis elements are indexed by sets corresponding to an intermediary statistic between peak and descent sets of permutations that we call extended peak., Comment: 12 pages; extended abstract submitted for FPSAC. Longform papers on the project are still forthcoming

In 1930, Tammes posed the problem of determining $\rho(r, n)$, the minimum over all sets of $n$ unit vectors in $\mathbb{R}^r$ of their maximum pairwise inner product. In 1955, Rankin determined $\rho(r,n)$ whenever $n \leq 2r$ and in this paper we show that $\rho(r, 2r + k ) \geq \frac{\left(\frac{8}{27}k + 1\right)^{1/3} - 1}{2r + k}$, answering a question of Bukh and Cox. As a consequence, we conclude that the maximum size of a binary code with block length $r$ and minimum Hamming distance $(r-j)/2$ is at most $(2 + o(1))r$ when $j = o(r^{1/3})$, resolving a conjecture of Tiet\"av\"ainen from 1980 in a strong form. Furthermore, using a recently discovered connection to binary codes, this yields an analogous result for set-coloring Ramsey numbers of triangles., Comment: 6 pages

The notion of curvature on graphs has recently gained traction in the networks community, with the Ollivier-Ricci curvature (ORC) in particular being used for several tasks in network analysis, such as community detection. In this work, we choose a different approach and study augmentations of the discretization of the Ricci curvature proposed by Forman (AFRC). We empirically and theoretically investigate its relation to the ORC and the un-augmented Forman-Ricci curvature. In particular, we provide evidence that the AFRC frequently gives sufficient insight into the structure of a network to be used for community detection, and therefore provides a computationally cheaper alternative to previous ORC-based methods. Our novel AFRC-based community detection algorithm is competitive with an ORC-based approach. The codebase for fast and efficient computations of AFRC and the experiments in this article will be made publicly available upon publication., Comment: 22 pages, 11 figures

A simple graph is called triangular if every edge of it belongs to a triangle. We conjecture that any graphical degree sequence all terms of which are greater than or equal to 4 has a triangular realisation, and establish this conjecture for a class of biregular graphical degree sequences., Comment: 11 pages, 1 figure

The Tutte polynomial and Derksen's $\mathcal{G}$-invariant are the universal deletion/contraction and valuative matroid and polymatroid invariants, respectively. There are only a handful of well known invariants (like the matroid Kazhdan-Lusztig polynomials) between (in terms of roughness/fineness) the Tutte polynomial and Derksen's $\mathcal{G}$-invariant. The aim of this study is to define a spectrum of generalized Tutte polynomials to fill the gap between the Tutte polynomial and Derksen's $\mathcal{G}$-invariant. These polynomials are built by taking repeated convolution products of universal Tutte characters studied by Dupont, Fink, and Moci and using the framework of Ardila and Sanchez for studying valuative invariants. We develop foundational aspects of these polynomials by showing they are valuative on generalized permutahedra and present a generalized deletion/contraction formula. We apply these results on chain Tutte polynomials to obtain new formulas for the M\"obius polynomial, the opposite characteristic polynomial, a generalized M\"obius polynomial, Ford's expected codimension of a matroid variety, and Derksen's $\mathcal{G}$-invariant., Comment: 30 pages

Given two non-empty graphs $H$ and $T$, write $H\succcurlyeq T$ to mean that $t(H,G)^{|E(T)|}\geq t(T,G)^{|E(H)|}$ for every graph $G$, where $t(\cdot,\cdot)$ is the homomorphism density function. We obtain various necessary and sufficient conditions for two trees $H$ and $T$ to satisfy $H\succcurlyeq T$ and determine all such pairs on at most 8 vertices. This extends results of Leontovich and Sidorenko from the 1980s and 90s. Our approach applies an information-theoretic technique of Kopparty and Rossman to reduce the problem of showing that $H\succcurlyeq T$ for two forests $H$ and $T$ to solving a particular linear program. We also characterize trees $H$ which satisfy $H\succcurlyeq S_k$ or $H\succcurlyeq P_4$, where $S_k$ is the $k$-vertex star and $P_4$ is the $4$-vertex path., Comment: 53 pages

We consider the statistics of extreme eigenvalues of random $d$-regular graphs, with $N^{\mathfrak c}\leq d\leq N^{1/3-{\mathfrak c}}$ for arbitrarily small ${\mathfrak c}>0$. We prove that in this regime, the fluctuations of extreme eigenvalues are given by the Tracy-Widom distribution. As a consequence, about 69% of $d$-regular graphs have all nontrivial eigenvalues bounded in absolute value by $2\sqrt{d-1}$., 53 pages, 3 figures

A subset $M$ of the edges of a graph or hypergraph is hitting if $M$ covers each vertex of $H$ at least once, and $M$ is $t$-shallow if it covers each vertex of $H$ at most $t$ times. We consider the existence of shallow hitting edge sets and the maximum size of shallow edge sets in $r$-uniform hypergraph $H$ that are regular or have a large minimum degree. Specifically, we show the following. Every $r$-uniform regular hypergraph has a $t$-shallow hitting edge set with $t = O(r)$. Every $r$-uniform regular hypergraph with $n$ vertices has a $t$-shallow edge set of size $\Omega(nt/r^{1+1/t})$. Every $r$-uniform hypergraph with $n$ vertices and minimum degree $\delta_{r-1}(H) \geq n/((r-1)t+1)$ has a $t$-shallow hitting edge set. Every $r$-uniform $r$-partite hypergraph with $n$ vertices in each part and minimum degree $\delta'_{r-1}(H) \geq n/((r-1)t+1) +1$ has a $t$-shallow hitting edge set. We complement our results with constructions of $r$-uniform hypergraphs that show that most of our obtained bounds are best-possible.

If $G$ is a simple graph and $\rho\in[0,1]$, the reliability $R_G(\rho)$ is the probability of $G$ being connected after each of its edges is removed independently with probability $\rho$. A simple graph $G$ is a \emph{uniformly most reliable graph} (UMRG) if $R_G(\rho)\geq R_H(\rho)$ for every $\rho\in[0,1]$ and every simple graph $H$ on the same number of vertices and edges as $G$. Boesch [J.\ Graph Theory 10 (1986), 339--352] conjectured that, if $n$ and $m$ are such that there exists a connected simple graph on $n$ vertices and $m$ edges, then there also exists a UMRG on the same number of vertices and edges. Some counterexamples to Boesch's conjecture were given by Kelmans, Myrvold et al., and Brown and Cox. It is known that Boesch's conjecture holds whenever the corank, defined as $c=m-n+1$, is at most $4$ (and the corresponding UMRGs are fully characterized). Ath and Sobel conjectured that Boesch's conjecture holds whenever the corank $c$ is between $5$ and $8$, provided the number of vertices is at least $2c-2$. In this work, we give an infinite family of counterexamples to Boesch's conjecture of corank $5$. These are the first reported counterexamples that attain the minimum possible corank. As a byproduct, the conjecture by Ath and Sobel is disproved., Comment: 15 pages, 6 figures

We explore some connections between vectors of integers and integer partitions seen as bi-infinite words. This methodology enables us to give a combinatorial interpretation of the Macdonald identities for affine root systems of the seven infinite families in terms of symplectic and special orthogonal Schur functions. From these results, we are able to derive $q$-Nekrasov--Okounkov formulas associated to each family. Nevertheless we only give results for types $\tilde{C}$ and $\tilde{C}^{\vee}$, and give a sketch of the proof for type $\tilde{C}$., Comment: 10 pages, this is an extended abstract

Delta-matroids are "type B" generalizations of matroids in the same way that maximal orthogonal Grassmannians are generalizations of Grassmannians. A delta-matroid analogue of the Tutte polynomial of a matroid is the interlace polynomial. We give a geometric interpretation for the interlace polynomial via the K-theory of maximal orthogonal Grassmannians. To do so, we develop a new Hirzebruch-Riemann-Roch-type formula for the type B permutohedral variety., Comment: 19 pages

Let be the symmetric functions defined for the pair of integers $\left( n,r\right) $ $n\geq r\geq 1$ by $p_{n}^{\left( r\right) }=\sum m_{\lambda }$ where $m_{\lambda }$ are the monomial symmetric functions, the sum being over the partitions $\lambda $ of the integer $n$ of length $r$. In this article we introduce a $q$-analog of $p_{n}^{\left( r\right) }$, through generating functions and give some of its properties which are $q$-analogs of its classical correspondent in particular when $r=1$. It is proved that this $q$-analog of $p_{n}^{\left( r\right) }$ can be expressed in terms of the classical $p_{n}^{\left( j\right) }$, through the $q$-Stirling numbers of the second kind. We also begin, with the same procedure, the study of a $p,q$-analog of $p_{n}^{\left( r\right) }$. In the rest of the article we specialize in the series $\sum\nolimits_{n=0}^{\infty }q^{\binom{n}{2}}t^{n}/n!$ . We show that $p_{n}^{\left( r\right) }$ is then related to the $q^{r}$-analog of $p_{n-r}$. The existence of a double sequence of polynomials with integer coefficients, denoted $J_{n,r}\left( q\right) $, is deduced. We identify these polynomials with the inversion enumerators introduced for specific rooted forests. These polynomials verify a ''positive'' linear recurrence which allows to build row by row the table of $J_{n,r}$ from the initial conditions $J_{r,r}=1$. The form of the linear recurrence is given for the reciprocal polynomials of \ $J_{n,r}$, which are the sum enumerators of parking functions. The linear recurrence permits to obtain an explicit calculation formula for $J_{n,r}$ . This formula leads us to introduce new statistics on rooted trees and forests for $\ J_{n,r}$ or its reciprocal., Comment: 17 pages, 1 figure. All the results are unchanged. Minor changes to improve English and writing of the text. One reference added and modification of the numbering of references. Equation (2.1) corrected. Section 5: Open problem replaced by Remark and shorcut. Lemma 6.1 replaced by Proposition 6.1, content unchanged. An additional paragraph in the conclusion. Change of legend of Figure 1

Let $(\mathcal{F},\mathcal{G})$ be a pair of families of $[n]$, where $[n]=\{1,2,...,n\}$. If $A\not\subset B$ and $B\not\subset A$ hold for all $A\in\mathcal{F}$ and $B\in\mathcal{G}$, then $(\mathcal{F},\mathcal{G})$ is called a Cross-Sperner pair. P. Frankl and Jian Wang introduced the extremal problem that $m(n)={\rm{max}}\{|\mathcal{I}(\mathcal{F},\mathcal{G})|:\mathcal{F},\mathcal{G}\subset2^{[n]}~{\rm{are~cross}}$-${\rm{sperner}}\}$, where $\mathcal{I}(\mathcal{F},\mathcal{G})=\{A\cap B:A\in\mathcal{F},B\in\mathcal{G}\}$. In this note, we prove that $m(n)=2^n-2^{\lfloor\frac{n}{2}\rfloor}-2^{\lceil\frac{n}{2}\rceil}+1$ for all $n>1$. This solves an open problem proposed by P. Frankl and Jian Wang., We solve an open problem proposed by P. Frankl and Jian Wang