bluuebunny/crossref_metadata_2025 huggingface dataset:
The extended equivalence and equation solvability problems for groups
Authors: Horvath Gabor , Szabo Csaba
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

We prove that the extended equivalence problem is solvable in polynomial time for finite nilpotent groups, and coNP-complete, otherwise. We prove that the extended equation solvability problem is solvable in polynomial time for finite nilpotent groups, and NP-complete, otherwise.
On packing of two copies of a hypergraph
Authors: Pilsniak Monika , WoźniaK Mariusz
Published: August 2021

Graphs and Algorithms

A 2-packing of a hypergraph H is a permutation sigma on V (H) such that if an edge e belongs to epsilon(H), then sigma(e) does not belong to epsilon(H). Let H be a hypergraph of order n which contains edges of cardinality at least 2 and at most n - 2. We prove that if H has at most n - 2 edges then it is 2-packable.
A Combinatorial Approach to the Tanny Sequence
Authors: Das Anita
Published: August 2021

Combinatorics

The Tanny sequence T (i) is a sequence defined recursively as T(i) = T(i - 1 - T(i - 1)) + T(i - 2 - T(i - 2)), T(0) = T(1) = T(2) = 1. In the first part of this paper we give combinatorial proofs of all the results regarding T(i), that Tanny proved in his paper "A well-behaved cousin of the Hofstadter sequence", Discrete Mathematics, 105(1992), pp. 227-239, using algebraic means. In most cases our proofs turn out to be simpler and shorter. Moreover, they give a "visual" appeal to the theory developed by Tanny. We also generalize most of Tanny's results. In the second part of the paper we present many new results regarding T(i) and prove them combinatorially. Given two integers n and k, it is interesting to know if T(n) = k or not. In this paper we characterize such numbers.
Colouring the Square of the Cartesian Product of Trees
Authors: Wood David R.
Published: August 2021

Graphs and Algorithms

We prove upper and lower bounds on the chromatic number of the square of the cartesian product of trees. The bounds are equal if each tree has even maximum degree.
On the sensitivity of cyclically-invariant Boolean functions
Authors: Chakraborty Sourav
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

In this paper we construct a cyclically invariant Boolean function whose sensitivity is Theta(n(1/3)). This result answers two previously published questions. Turan (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Omega(root n). Kenyon and Kutin (2004) asked whether for a "nice" function the product of 0-sensitivity and 1-sensitivity is Omega(n). Our function answers both questions in the negative. We also prove that for minterm-transitive functions (a natural class of Boolean functions including our example) the sensitivity is Omega(n(1/3)). Hence for this class of functions sensitivity and block sensitivity are polynomially related.
Digital search trees with m trees: Level polynomials and insertion costs
Authors: Prodinger Helmut
Published: August 2021

Analysis of Algorithms

We adapt a novel idea of Cichon's related to Approximate Counting to the present instance of Digital Search Trees, by using m (instead of one) such trees. We investigate the level polynomials, which have as coefficients the expected numbers of data on a given level, and the insertion costs. The level polynomials can be precisely described, thanks to formulae from q-analysis. The asymptotics of expectation and variance of the insertion cost are fairly standard these days and done with Rice's method.
An expected polynomial time algorithm for coloring 2-colorable 3-graphs
Authors: Person Yury , Schacht Mathias
Published: August 2021

Graphs and Algorithms

We present an algorithm that for 2-colorable 3-uniform hypergraphs, finds a 2-coloring in average running time O (n(5) log(2) n).
Avoidance colourings for small nonclassical Ramsey numbers
Authors: Burger Alewyn Petrus , Vuuren Jan H.
Published: August 2021

Graphs and Algorithms

The irredundant Ramsey number s - s(m, n) [upper domination Ramsey number u - u(m, n), respectively] is the smallest natural number s [u, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order s [u, respectively], it holds that IR(B) \textgreater= m or IR(R) \textgreater= n [Gamma (B) \textgreater= m or Gamma(R) \textgreater= n, respectively], where Gamma and IR denote respectively the upper domination number and the irredundance number of a graph. Furthermore, the mixed irredundant Ramsey number t = t(m, n) [mixed domination Ramsey number v = v(m, n), respectively] is the smallest natural number t [v, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order t [v, respectively], it holds that IR(B) \textgreater= m or beta(R) \textgreater= n [Gamma(B) \textgreater= m or beta(R) \textgreater= n, respectively], where beta denotes the independent domination number of a graph. These four classes of non-classical Ramsey numbers have previously been studied in the literature. In this paper we introduce a new Ramsey number w = w(m, n), called the irredundant-domination Ramsey number, which is the smallest natural number w such that in any red-blue edge colouring (R, B) of the complete graph of order w, it holds that IR(B) \textgreater= m or Gamma(R) \textgreater= n. A computer search is employed to determine complete sets of avoidance colourings of small order for these five classes of nonclassical Ramsey numbers. In the process the fifteen previously unknown Ramsey numbers t(4, 4) = 14, t(6, 3) = 17, u(4, 4) = 13, v(4, 3) = 8, v(4, 4) = 14, v(5, 3) = 13, v(6, 3) = 17, w(3, 3) = 6, w(3, 4) = w(4, 3) = 8, w(4, 4) = 13, w(3, 5) = w(5, 3) = 12 and w(3, 6) = w(6, 3) = 15 are established.
New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree
Authors: Zhang Xin , Wu Jian-Liang , Liu Guizhen
Published: August 2021

Combinatorics

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph of minimum degree 6 contains a copy of 4-cycle with all vertices of degree at most 19. In addition, we also show that the complete graph K 4 is light in the family of 1-planar graphs of minimum degree 7, with its height at most 11.
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set
Authors: Gaspers Serge , Liedloff Mathieu
Published: August 2021

Graphs and Algorithms

An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower bound of \Omega(1.3247^n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.
On hamiltonian chain saturated uniform hypergraphs
Authors: Dudek Aneta , Zak Andrzej
Published: August 2021

Graphs and Algorithms

We say that a hypergraph H is hamiltonian chain saturated if H does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H. In this paper we ask about the smallest size of a k-uniform hamiltonian chain saturated hypergraph. We present a construction of a family of k-uniform hamiltonian chain saturated hypergraphs with O(n(k-1/2)) edges.
Adaptive Identification of Sets of Vertices in Graphs
Authors: Junnila Ville
Published: August 2021

Combinatorics

In this paper, we consider a concept of adaptive identification of vertices and sets of vertices in different graphs, which was recently introduced by Ben-Haim, Gravier, Lobstein and Moncel (2008). The motivation for adaptive identification comes from applications such as sensor networks and fault detection in multiprocessor systems. We present an optimal adaptive algorithm for identifying vertices in cycles. We also give efficient adaptive algorithms for identifying sets of vertices in different graphs such as cycles, king lattices and square lattices. Adaptive identification is also considered in Hamming spaces, which is one of the most widely studied graphs in the field of identifying codes.
Random Horn formulas and propagation connectivity for directed hypergraphs
Authors: Sloan Robert H. , Stasi Despina , Turán György
Published: August 2021

Combinatorics

We consider the property that in a random definite Horn formula of size-3 clauses over n variables, where every such clause is included with probability p, there is a pair of variables for which forward chaining produces all other variables. We show that with high probability the property does not hold for p <= 1/(11n ln n), and does hold for p >= (5 1n ln n)/(n ln n).
A note on planar Ramsey numbers for a triangle versus wheels
Authors: Zhou Guofei , Chen Yaojun , Miao Zhengke , Pirzada Shariefuddin
Published: August 2021

Graph Theory

For two given graphs G and H , the planar Ramsey number P R ( G; H ) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G , or its complement contains a copy of H . In this paper, we determine all planar Ramsey numbers for a triangle versus wheels.
On paths, trails and closed trails in edge-colored graphs
Authors: Gourvès Laurent , Lyra Adria , Martinhon Carlos A. , Monnot Jérôme
Published: August 2021

Graph Theory

In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in G(c), we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp., trails) in G(c) with endpoints in S. Further, if G(c) contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles. We also deal with graphs G(c) containing no (almost) PEC cycles or closed trails through s or t. We prove that finding 2 PEC s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the PEC path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since as proved in Abouelaoualim et. al.(2008), the determination of two or more vertex disjoint PEC s-t paths can be done in polynomial time. Finally, if G(c) is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.
Weak equivalence of higher-dimensional automata
Authors: Kahl Thomas
Published: August 2021

This paper introduces a notion of equivalence for higher-dimensional
automata, called weak equivalence. Weak equivalence focuses mainly on a
traditional trace language and a new homology language, which captures the
overall independence structure of an HDA. It is shown that weak equivalence is
compatible with both the tensor product and the coproduct of HDAs and that,
under certain conditions, HDAs may be reduced to weakly equivalent smaller ones
by merging and collapsing cubes.
Random graphs with bounded maximum degree: asymptotic structure and a logical limit law
Authors: Koponen Vera
Published: August 2021

General

For any fixed integer R≥2 we characterise the typical structure of undirected graphs with vertices 1,...,n and maximum degree R, as n tends to infinity. The information is used to prove that such graphs satisfy a labelled limit law for first-order logic. If R≥5 then also an unlabelled limit law holds.
The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degree
Authors: Szymańska Edyta
Published: August 2021

Discrete Algorithms

In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c\binom|V(H)|-1r-1, or minimum degree of a pair of vertices at least c\binom|V(H)|-2r-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain first optimal dichotomy results for 2-colorings of r-uniform hypergraphs. For each problem, for every r≥q 3 we determine a threshold value depending on r such that the problem is NP-complete for c below the threshold, while for c strictly above the threshold it is polynomial. We provide an algorithm constructing the coloring with time complexity O(n^\lfloor 4/ε\rfloor+2\log n) with some ε>0. This algorithm becomes more efficient in the case of r=3,4,5 due to known Turán numbers of the triangle and the Fano plane. In addition, we determine the computational complexity of strong k-coloring of 3-uniform hypergraphs H with minimum vertex degree at least c\binom|V(H)|-12, for some c, leaving a gap for k≥q 5 which vanishes as k→ ∞.
Two examples of Wilf-collapse
Authors: Albert Michael , Jelínek Vít , Opler Michal
Published: August 2021

Two permutation classes, the X-class and subpermutations of the increasing
oscillation are shown to exhibit an exponential Wilf-collapse. This means that
the number of distinct enumerations of principal subclasses of each of these
classes grows much more slowly than the class itself whereas a priori, based
only on symmetries of the class, there is no reason to expect this. The
underlying cause of the collapse in both cases is the ability to apply some
form of local symmetry which, combined with a greedy algorithm for detecting
patterns in these classes, yields a Wilf-collapse.
Enumeration of Permutation Classes and Weighted Labelled Independent Sets
Authors: Bean Christian , Nadeau Émile , Ulfarsson Henning
Published: August 2021

In this paper, we study the staircase encoding of permutations, which maps a
permutation to a staircase grid with cells filled with permutations. We
consider many cases, where restricted to a permutation class, the staircase
encoding becomes a bijection to its image. We describe the image of those
restrictions using independent sets of graphs weighted with permutations. We
derive the generating function for the independent sets and then for their
weighted counterparts. The bijections we establish provide the enumeration of
permutation classes. We use our results to uncover some unbalanced
Wilf-equivalences of permutation classes and outline how to do random sampling
in the permutation classes. In particular, we cover the classes
$\mathrm{Av}(2314,3124)$, $\mathrm{Av}(2413,3142)$, $\mathrm{Av}(2413,3124)$,
$\mathrm{Av}(2413,2134)$ and $\mathrm{Av}(2314,2143)$, as well as many
subclasses.
Catalan words avoiding pairs of length three patterns
Authors: Baril Jean-Luc , Khalil Carine , Vajnovszki Vincent
Published: August 2021

Catalan words are particular growth-restricted words counted by the eponymous
integer sequence. In this article we consider Catalan words avoiding a pair of
patterns of length 3, pursuing the recent initiating work of the first and last
authors and of S. Kirgizov where (among other things) the enumeration of
Catalan words avoiding a patterns of length 3 is completed. More precisely, we
explore systematically the structural properties of the sets of words under
consideration and give enumerating results by means of recursive decomposition,
constructive bijections or bivariate generating functions with respect to the
length and descent number. Some of the obtained enumerating sequences are
known, and thus the corresponding results establish new combinatorial
interpretations for them.
Topological structuring of the digital plane
Authors: Šlapal Josef
Published: August 2021

Combinatorics

We discuss an Alexandroff topology on ℤ2 having the property that its quotient topologies include the Khalimsky and Marcus-Wyse topologies. We introduce a further quotient topology and prove a Jordan curve theorem for it.
Probe interval graphs and probe unit interval graphs on superclasses of cographs
Authors: Bonomo Flavia , Durán Guillermo , Grippo Luciano N. , Safe Martın D.
Published: August 2021

Graph Theory

A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe G) graphs with disconnected complement for every graph class G with a companion.
Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs
Authors: Gosselin Shonda , Szymański Andrzej , Wojda Adam Pawel
Published: August 2021

Combinatorics

A \em cyclic q-partition of a hypergraph (V,E) is a partition of the edge set E of the form \F,F^θ,F^θ², \ldots, F^θ^q-1\ for some permutation θ of the vertex set V. Let Vₙ = \ 1,2,\ldots,n\. For a positive integer k, Vₙ\choose k denotes the set of all k-subsets of Vₙ. For a nonempty subset K of V_n-1, we let \mathcalKₙ^(K) denote the hypergraph ≤ft(Vₙ, \bigcup_k∈ K Vₙ\choose k\right). In this paper, we find a necessary and sufficient condition on n, q and k for the existence of a cyclic q-partition of \mathcalKₙ^(V_k). In particular, we prove that if p is prime then there is a cyclic p^α-partition of \mathcalK^(Vₖ)ₙ if and only if p^α + β divides n, where β = \lfloor \logₚ k\rfloor. As an application of this result, we obtain two sufficient conditions on n₁,n₂,\ldots,n_t, k, α and a prime p for the existence of a cyclic p^α-partition of the complete t-partite k-uniform hypergraph \mathcal K^(k)_n₁,n₂,\ldots,n_t.
Maximal independent sets in bipartite graphs with at least one cycle
Authors: Li Shuchao , Zhang Huihui , Zhang Xiaoyan
Published: August 2021

Graph Theory

A maximal independent set is an independent set that is not a proper subset of any other independent set. Liu [J.Q. Liu, Maximal independent sets of bipartite graphs, J. Graph Theory, 17 (4) (1993) 495-507] determined the largest number of maximal independent sets among all n-vertex bipartite graphs. The corresponding extremal graphs are forests. It is natural and interesting for us to consider this problem on bipartite graphs with cycles. Let \mathscrBₙ (resp. \mathscrBₙ') be the set of all n-vertex bipartite graphs with at least one cycle for even (resp. odd) n. In this paper, the largest number of maximal independent sets of graphs in \mathscrBₙ (resp. \mathscrBₙ') is considered. Among \mathscrBₙ the disconnected graphs with the first-, second-, \ldots, \fracn-22-th largest number of maximal independent sets are characterized, while the connected graphs in \mathscrBₙ having the largest, the second largest number of maximal independent sets are determined. Among \mathscrBₙ' graphs have the largest number of maximal independent sets are identified.
Destroying Bicolored $P_3$s by Deleting Few Edges
Authors: Grüttemeier Niels , Komusiewicz Christian , Schestag Jannik , Sommer Frank
Published: August 2021

We introduce and study the Bicolored $P_3$ Deletion problem defined as
follows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitioned
into a set $E_r$ of red edges and a set $E_b$ of blue edges. The question is
whether we can delete at most $k$ edges such that $G$ does not contain a
bicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path on
three vertices with one blue and one red edge. We show that Bicolored $P_3$
Deletion is NP-hard and cannot be solved in $2^{o(|V|+|E|)}$ time on
bounded-degree graphs if the ETH is true. Then, we show that Bicolored $P_3$
Deletion is polynomial-time solvable when $G$ does not contain a bicolored
$K_3$, that is, a triangle with edges of both colors. Moreover, we provide a
polynomial-time algorithm for the case that $G$ contains no blue $P_3$, red
$P_3$, blue $K_3$, and red $K_3$. Finally, we show that Bicolored $P_3$
Deletion can be solved in $ O(1.84^k\cdot |V| \cdot |E|)$ time and that it
admits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ is
the maximum degree of $G$.
Improved bounds on the crossing number of butterfly network
Authors: Manuel Paul D. , Rajan Bharati , Rajasingh Indra , Beulah P. Vasanthi
Published: August 2021

Graph Theory

We draw the r-dimensional butterfly network with 1 / 44r+O(r2r) crossings which improves the previous estimate given by Cimikowski (1996). We also give a lower bound which matches the upper bound obtained in this paper.
On the connectedness and diameter of a geometric Johnson graph
Authors: Bautista-Santiago Crevel , Cano Javier , Fabila-Monroy Ruy , Flores-Peñaloza David , González-Aguilar Hernàn , Lara Dolores , Sarmiento Eliseo , Urrutia Jorge
Published: August 2021

Combinatorics

Let P be a set of n points in general position in the plane. A subset I of P is called an island if there exists a convex set C such that I = P \C. In this paper we define the generalized island Johnson graph of P as the graph whose vertex consists of all islands of P of cardinality k, two of which are adjacent if their intersection consists of exactly l elements. We show that for large enough values of n, this graph is connected, and give upper and lower bounds on its diameter.
1-local 33/24-competitive Algorithm for Multicoloring Hexagonal Graphs
Authors: Witkowski Rafal , Žerovnik Janez
Published: August 2021

Graph Theory

In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by assigned frequencies, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph, where each vertex knows its position in the graph. We present a 1-local 33/24-competitive distributed algorithm for multicoloring a hexagonal graph, thereby improving the previous 1-local 7/5-competitive algorithm.
The resolving number of a graph Delia
Authors: Garijo Delia , González Antonio , Márquez Alberto
Published: August 2021

Graph Theory

We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: while computing the metric dimension of an arbitrary graph is known to be NP-hard, we show that the resolving number can be computed in polynomial time. We then relate the resolving number to classical graph parameters: diameter, girth, clique number, order and maximum degree. With these relations in hand, we characterize the graphs with resolving number 3 extending other studies that provide characterizations for smaller resolving number.
Two player game variant of the Erd\H os-Szekeres problem
Authors: Kolipaka Parikshit , Govindarajan Sathish
Published: August 2021

Combinatorics

The classical Erd˝os-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erd˝os-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdös-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations
Krausz dimension and its generalizations in special graph classes
Authors: Glebova Olga , Metelsky Yury , Skums Pavel
Published: August 2021

Graph Theory

A Krausz (k,m)-partition of a graph G is a decomposition of G into cliques, such that any vertex belongs to at most k cliques and any two cliques have at most m vertices in common. The m-Krausz dimension kdimm(G) of the graph G is the minimum number k such that G has a Krausz (k,m)-partition. In particular, 1-Krausz dimension or simply Krausz dimension kdim(G) is a well-known graph-theoretical parameter. In this paper we prove that the problem "kdim(G)≤3" is polynomially solvable for chordal graphs, thus partially solving the open problem of P. Hlineny and J. Kratochvil. We solve another open problem of P. Hlineny and J. Kratochvil by proving that the problem of finding Krausz dimension is NP-hard for split graphs and complements of bipartite graphs. We show that the problem of finding m-Krausz dimension is NP-hard for every m≥1, but the problem "kdimm(G)≤k" is is fixed-parameter tractable when parameterized by k and m for (∞,1)-polar graphs. Moreover, the class of (∞,1)-polar graphs with kdimm(G)≤k is characterized by a finite list of forbidden induced subgraphs for every k,m≥1.
List edge and list total colorings of planar graphs without non-induced 7-cycles
Authors: Dong Aijun , Liu Guizhen , Li Guojun
Published: August 2021

Graphs and Algorithms

Giving a planar graph G, let χ'l(G) and χ''l(G) denote the list edge chromatic number and list total chromatic number of G respectively. It is proved that if G is a planar graph without non-induced 7-cycles, then χ'l(G)≤Δ(G)+1 and χ''l(G)≤Δ(G)+2 where Δ(G)≥7.
The b-chromatic number of powers of cycles
Authors: Kohl Anja
Published: August 2021

Graph Theory

A b-coloring of a graph G by k colors is a proper vertex coloring such that each color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number χb(G) is the maximum integer k for which G has a b-coloring by k colors. Let Cnr be the rth power of a cycle of order n. In 2003, Effantin and Kheddouci established the b-chromatic number χb(Cnr) for all values of n and r, except for 2r+3≤n≤3r. For the missing cases they presented the lower bound L:= min n-r-1,r+1+⌊ n-r-1 / 3⌋ and conjectured that χb(Cnr)=L. In this paper, we determine the exact value on χb(Cnr) for the missing cases. It turns out that χb(Cnr)>L for 2r+3≤n≤2r+3+r-6 / 4.
Cumulants of Jack symmetric functions and b-conjecture (extended abstract)
Authors: Dolega Maciej , Féray Valentin
Published: August 2021

Goulden and Jackson (1996) introduced, using Jack symmetric functions, some multivariate generating series ψ(x, y, z; t, 1 + β) that might be interpreted as a continuous deformation of the rooted hypermap generating series. They made the following conjecture: coefficients of ψ(x, y, z; t, 1+β) are polynomials in β with nonnegative integer coefficients. We prove partially this conjecture, nowadays called b-conjecture, by showing that coefficients of ψ(x, y, z; t, 1 + β) are polynomials in β with rational coefficients. Until now, it was only known that they are rational functions of β. A key step of the proof is a strong factorization property of Jack polynomials when α → 0 that may be of independent interest.
Decomposition of the product of a monomial and a Demazure atom
Authors: Ying Pun Anna
Published: August 2021

We prove that the product of a monomial and a Demazure atom is a positive sum of Demazure atoms combinatorially. This result proves one particular case in a conjecture which provides an approach to a combinatorial proof of Schubert positivity property.
A non-partitionable Cohen–Macaulay simplicial complex
Authors: Duval Art M. , Goeckner Bennet , Klivans Caroline J. , Martin Jeremy
Published: August 2021

A long-standing conjecture of Stanley states that every Cohen–Macaulay simplicial complex is partition- able. We disprove the conjecture by constructing an explicit counterexample. Due to a result of Herzog, Jahan and Yassemi, our construction also disproves the conjecture that the Stanley depth of a monomial ideal is always at least its depth.
Asymptotics of polygons in restricted geometries subject to a force
Authors: Beaton Nicholas , Eng Jeremy , Soteros Christine
Published: August 2021

We consider self-avoiding polygons in a restricted geometry, namely an infinite L × M tube in Z3. These polygons are subjected to a force f, parallel to the infinite axis of the tube. When f > 0 the force stretches the polygons, while when f < 0 the force is compressive. In this extended abstract we obtain and prove the asymptotic form of the free energy in the limit f → −∞. We conjecture that the f → −∞ asymptote is the same as the free energy of Hamiltonian polygons, which visit every vertex in a L × M × N box.
DHD-puzzles
Authors: Beil Sabine
Published: August 2021

In this work triangular puzzles that are composed of unit triangles with labelled edges are considered. To be more precise, the labelled unit triangles that we allow are on the one hand the puzzle pieces that compute Schubert calculus and on the other hand the flipped K-theory puzzle piece. The motivation for studying such puzzles comes from the fact that they correspond to a class of oriented triangular fully packed loop configurations. The main result that is presented is an expression for the number of these puzzles with a fixed boundary in terms of Littlewood- Richardson coefficients.
Quasisymmetric functions from combinatorial Hopf monoids and Ehrhart Theory
Authors: White Jacob
Published: August 2021

We investigate quasisymmetric functions coming from combinatorial Hopf monoids. We show that these invariants arise naturally in Ehrhart theory, and that some of their specializations are Hilbert functions for relative simplicial complexes. This class of complexes, called forbidden composition complexes, also forms a Hopf monoid, thus demonstrating a link between Hopf algebras, Ehrhart theory, and commutative algebra. We also study various specializations of quasisymmetric functions.
Scheduling Problems and Generalized Graph Coloring
Authors: Machacek John
Published: August 2021

We define a new type of vertex coloring which generalizes vertex coloring in graphs, hypergraphs, andsimplicial complexes. To this coloring there is an associated symmetric function in noncommuting variables for whichwe give a deletion-contraction formula. In the case of graphs our symmetric function in noncommuting variablesagrees with the chromatic symmetric function in noncommuting variables of Gebhard and Sagan. Our vertex coloringis a special case of the scheduling problems defined by Breuer and Klivans. We show how the deletion-contractionlaw can be applied to scheduling problems.
Symmetric matrices, Catalan paths, and correlations
Authors: Tsukerman Emmanuel , Williams Lauren , Sturmfels Bernd
Published: August 2021

Kenyon and Pemantle (2014) gave a formula for the entries of a square matrix in terms of connected principal and almost-principal minors. Each entry is an explicit Laurent polynomial whose terms are the weights of domino tilings of a half Aztec diamond. They conjectured an analogue of this parametrization for symmetric matrices, where the Laurent monomials are indexed by Catalan paths. In this paper we prove the Kenyon-Pemantle conjecture, and apply this to a statistics problem pioneered by Joe (2006). Correlation matrices are represented by an explicit bijection from the cube to the elliptope.
Fully packed loop configurations : polynomiality and nested arches
Authors: Aigner Florian
Published: August 2021

This extended abstract proves that the number of fully packed loop configurations whose link pattern consists of two noncrossing matchings separated by m nested arches is a polynomial in m. This was conjectured by Zuber (2004) and for large values of m proved by Caselli et al. (2004)
The Smith normal form distribution of a random integer matrix
Authors: Wang Yinghui , Stanley Richard P.
Published: August 2021

We show that the density μ of the Smith normal form (SNF) of a random integer matrix exists and equals a product of densities μps of SNF over Z/psZ with p a prime and s some positive integer. Our approach is to connect the SNF of a matrix with the greatest common divisors (gcds) of certain polynomials of matrix entries, and develop the theory of multi-gcd distribution of polynomial values at a random integer vector. We also derive a formula for μps and determine the density μ for several interesting types of sets.
Defining amplituhedra and Grassmann polytopes
Authors: Karp Steven N.
Published: August 2021

The totally nonnegative Grassmannian Gr≥0 k,n is the set of k-dimensional subspaces V of Rn whose nonzero Plucker coordinates all have the same sign. In their study of scattering amplitudes in N = 4 supersym- metric Yang-Mills theory, Arkani-Hamed and Trnka (2013) considered the image (called an amplituhedron) of Gr≥0 k,n under a linear map Z : Rn → Rr, where k ≤ r and the r × r minors of Z are all positive. One reason they required this positivity condition is to ensure that the map Gr≥0 k,n → Grk,r induced by Z is well defined, i.e. it takes everynelement of Gr≥0 k,n to a k-dimensional subspace of Rr. Lam (2015) gave a sufficient condition for the induced map Gr≥0 k,n → Grk,r to be well defined, in which case he called the image a Grassmann polytope. (In the case k = 1, Grassmann polytopes are just polytopes, and amplituhedra are cyclic polytopes.) We give a necessary and sufficient condition for the induced map Gr≥0 k,n → Grk,r to be well defined, in terms of sign variation. Using previous work we presented at FPSAC 2015, we obtain an equivalent condition in terms of the r × r minors of Z (assuming Z has rank r).
On the enumeration of d-minimal permutations
Authors: Bouvel Mathilde , Ferrari Luca
Published: August 2021

We suggest an approach for the enumeration of minimal permutations having d descents which uses skew Young tableaux. We succeed in finding a general expression for the number of such permutations in terms of (several) sums of determinants. We then generalize the class of skew Young tableaux under consideration; this allows in particular to discover some presumably new results concerning Eulerian numbers.
McKay Centralizer Algebras
Authors: Benkart Georgia , Halverson Tom
Published: August 2021

For a finite subgroup G of the special unitary group SU2, we study the centralizer algebra Zk(G) = EndG(V⊗k) of G acting on the k-fold tensor product of its defining representation V = C2. The McKay corre- spondence relates the representation theory of these groups to an associated affine Dynkin diagram, and we use this connection to study the structure and representation theory of Zk(G) via the combinatorics of the Dynkin diagram. When G equals the binary tetrahedral, octahedral, or icosahedral group, we exhibit remarkable connections between Zk (G) and the Martin-Jones set partition algebras.
Almost simplicial polytopes: the lower and upper bound theorems
Authors: Nevo Eran , Pineda-Villavicencio Guillermo , Ugon Julien , Yost David
Published: August 2021

this is an extended abstract of the full version. We study n-vertex d-dimensional polytopes with at most one nonsimplex facet with, say, d + s vertices, called almost simplicial polytopes. We provide tight lower and upper bounds for the face numbers of these polytopes as functions of d, n and s, thus generalizing the classical Lower Bound Theorem by Barnette and Upper Bound Theorem by McMullen, which treat the case s = 0. We characterize the minimizers and provide examples of maximizers, for any d.
Yang-Baxter basis of Hecke algebra and Casselman's problem (extended abstract)
Authors: Nakasuji Maki , Naruse Hiroshi
Published: August 2021

We generalize the definition of Yang-Baxter basis of type A Hecke algebra introduced by A.Lascoux, B.Leclerc and J.Y.Thibon (Letters in Math. Phys., 40 (1997), 75–90) to all the Lie types and prove their duality. As an application we give a solution to Casselman's problem on Iwahori fixed vectors of principal series representation of p-adic groups.
Schur-positivity via products of grid classes
Authors: Elizalde Sergi , Roichman Yuval
Published: August 2021

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 Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition
Authors: Smith Jason P
Published: August 2021

The poset P of all permutations ordered by pattern containment is a fundamental object of study in the field of permutation patterns. This poset has a very rich and complex topology and an understanding of its Möbius function has proved particularly elusive, although results have been slowly emerging in the last few years. Using a variety of topological techniques we present a two term formula for the Mo ̈bius function of intervals in P. The first term in this formula is, up to sign, the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is (still) complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. This is thus the first polynomial time formula for the Möbius function of what appears to be a large proportion of all intervals of P.
Combinatorial descriptions of the crystal structure on certain PBW bases
Authors: Salisbury Ben , Schultze Adam , Tingley Peter
Published: August 2021

Lusztig's theory of PBW bases gives a way to realize the crystal B(∞) for any simple complex Lie algebra where the underlying set consists of Kostant partitions. In fact, there are many different such realizations, one for each reduced expression for the longest element of the Weyl group. There is an algorithm to calculate the actions of the crystal operators, but it can be quite complicated. For ADE types, we give conditions on the reduced expression which ensure that the corresponding crystal operators are given by simple combinatorial bracketing rules. We then give at least one reduced expression satisfying our conditions in every type except E8, and discuss the resulting combinatorics. Finally, we describe the relationship with more standard tableaux combinatorics in types A and D.
Oriented Flip Graphs and Noncrossing Tree Partitions
Authors: Garver Alexander , McConville Thomas
Published: August 2021

Given a tree embedded in a disk, we define two lattices - the oriented flip graph of noncrossing arcs and the lattice of noncrossing tree partitions. When the interior vertices of the tree have degree 3, the oriented flip graph is equivalent to the oriented exchange graph of a type A cluster algebra. Our main result is an isomorphism between the shard intersection order of the oriented flip graph and the lattice of noncrossing tree partitions. As a consequence, we deduce a simple characterization of c-matrices of type A cluster algebras.
The Delta Conjecture
Authors: Haglund James , Remmel Jeffrey B. , Wilson Andrew Timothy
Published: August 2021

We conjecture two combinatorial interpretations for the symmetric function ∆eken, where ∆f is an eigenoperator for the modified Macdonald polynomials defined by Bergeron, Garsia, Haiman, and Tesler. Both interpretations can be seen as generalizations of the Shuffle Conjecture, a statement originally conjectured by Haglund, Haiman, Remmel, Loehr, and Ulyanov and recently proved by Carlsson and Mellit. We show how previous work of the second and third authors on Tesler matrices and ordered set partitions can be used to verify several cases of our conjectures. Furthermore, we use a reciprocity identity and LLT polynomials to prove another case. Finally, we show how our conjectures inspire 4-variable generalizations of the Catalan numbers, extending work of Garsia, Haiman, and the first author.
The Prism tableau model for Schubert polynomials
Authors: Weigandt Anna , Yong Alexander
Published: August 2021

The Schubert polynomials lift the Schur basis of symmetric polynomials into a basis for Z[x1; x2; : : :]. We suggest the prism tableau model for these polynomials. A novel aspect of this alternative to earlier results is that it directly invokes semistandard tableaux; it does so as part of a colored tableau amalgam. In the Grassmannian case, a prism tableau with colors ignored is a semistandard Young tableau. Our arguments are developed from the Gr¨obner geometry of matrix Schubert varieties.
Total positivity for the Lagrangian Grassmannian
Authors: Karpman Rachel
Published: August 2021

The positroid decomposition of the Grassmannian refines the well-known Schubert decomposition, and has a rich combinatorial structure. There are a number of interesting combinatorial posets which index positroid varieties,just as Young diagrams index Schubert varieties. In addition, Postnikov’s boundary measurement map gives a family of parametrizations for each positroid variety. The domain of each parametrization is the space of edge weights of a weighted planar network. The positroid stratification of the Grassmannian provides an elementary example of Lusztig’s theory of total non negativity for partial flag varieties, and has remarkable applications to particle physics.We generalize the combinatorics of positroid varieties to the Lagrangian Grassmannian, the moduli space of maximal isotropic subspaces with respect to a symplectic form
Matrix-Ball Construction of affine Robinson-Schensted correspondence
Authors: Chmutov Michael , Pylyavskyy Pavlo , Yudovina Elena
Published: August 2021

In his study of Kazhdan-Lusztig cells in affine type A, Shi has introduced an affine analog of Robinson- Schensted correspondence. We generalize the Matrix-Ball Construction of Viennot and Fulton to give a more combi- natorial realization of Shi's algorithm. As a biproduct, we also give a way to realize the affine correspondence via the usual Robinson-Schensted bumping algorithm. Next, inspired by Honeywill, we extend the algorithm to a bijection between extended affine symmetric group and triples (P, Q, ρ) where P and Q are tabloids and ρ is a dominant weight. The weights ρ get a natural interpretation in terms of the Affine Matrix-Ball Construction. Finally, we prove that fibers of the inverse map possess a Weyl group symmetry, explaining the dominance condition on weights.
Normal Supercharacter Theory
Authors: Aliniaeifard Farid
Published: August 2021

There are three main constructions of supercharacter theories for a group G. The first, defined by Diaconis and Isaacs, comes from the action of a group A via automorphisms on our given group G. Another general way to construct a supercharacter theory for G, defined by Diaconis and Isaacs, uses the action of a group A of automor- phisms of the cyclotomic field Q[ζ|G|]. The third, defined by Hendrickson, is combining a supercharacter theories of a normal subgroup N of G with a supercharacter theory of G/N . In this paper we construct a supercharacter theory from an arbitrary set of normal subgroups of G. We show that when we consider the set of all normal subgroups of G, the corresponding supercharacter theory is related to a partition of G given by certain values on the central primitive idempotents. Also, we show the supercharacter theories that we construct can not be obtained via automorphisms or a single normal subgroup.
Strong parity vertex coloring of plane graphs
Authors: Kaiser Tomas , Rucky Ondrej , Stehlik Matej , Skrekovski Riste
Published: August 2021

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the coloring we construct is proper. This proves a conjecture of Czap and Jendrol' [Discuss. Math. Graph Theory 29 (2009), pp. 521-543.]. We also provide examples showing that eight colors may be necessary (ten when restricted to proper colorings).
Compatibility fans realizing graphical nested complexes
Authors: Manneville Thibault , Pilaud Vincent
Published: August 2021

Graph associahedra are polytopes realizing the nested complex N(G) on connected subgraphs of a graph G.While all known explicit constructions produce polytopes with the same normal fan, the great variety of fan realizationsof classical associahedra and the analogy between finite type cluster complexes and nested complexes incitedus to transpose S. Fomin and A. Zelevinsky's construction of compatibility fans for generalized associahedra (2003)to graph associahedra. Using a compatibility degree, we construct one fan realization of N(G) for each of its facets.Specifying G to paths and cycles, we recover a construction by F. Santos for classical associahedra (2011) and extendF. Chapoton, S. Fomin and A. Zelevinsky's construction (2002) for type B and C generalized associahedra.
Order Filter Model for Minuscule Plücker Relations
Authors: Lax David C
Published: August 2021

The Plücker relations which define the Grassmann manifolds as projective varieties are well known. Grass-mann manifolds are examples of minuscule flag manifolds. We study the generalized Plücker relations for minuscule flag manifolds independent of Lie type. To do this we combinatorially model the Plücker coordinates based on Wild-berger’s construction of minuscule Lie algebra representations; it uses the colored partially ordered sets known asminuscule posets. We obtain, uniformly across Lie type, descriptions of the Plücker relations of “extreme weight”. We show that these are “supported” by “double-tailed diamond” sublattices of minuscule lattices. From this, we obtain a complete set of Plücker relations for the exceptional minuscule flag manifolds. These Plücker relations are straightening laws for their coordinate rings.