The aim of this article is to motivate and describe the parameter ecology program, which studies how different parameters contribute to the difficulty of classical problems. We call for a new type of in parameterized analysis, with the purpose of uncovering the boundaries of tractability by finding the smallest possible parameterizations which admit FPT-algorithms or polynomial kernels. An extensive overview of recent advances on this front is presented for the problem. Moving even beyond the parameter ecology program we advocate the principle of model enrichment, which raises the challenge of generalizing positive results to problem definitions with greater modeling power. The computational intractability which inevitably emerges can be deconstructed by introducing additional parameters, leading towards a theory of fully multivariate algorithmics.
It is well known that if is a semihypergroup and is a strongly regular relation on , then , the set of equivalence classes, is a semigroup with the binary operation: for all . Now, let be an ordered semihypergroup. The following question is natural: Is there a strongly regular relation on for which is an ordered semigroup? One of our main aim in this paper is reply to the above question. Then, we study some properties and isomorphisms between them.
Using topological circles in the Freudenthal compactification of a graph as infinite cycles, we extend to locally finite graphs a result of Oberly and Sumner on the Hamiltonicity of finite graphs. This answers a question of Stein, and gives a sufficient condition for Hamiltonicity in locally finite graphs.
Let be a connected graph with maximum degree distinct from . Given integers and , is said to be -partitionable if there exists a partition of into sets such that is -degenerate for . In this paper, we prove that we can find a -partition of in -time whenever and . This generalizes a result of Bonamy et al. (2017) and can be viewed as an algorithmic extension of Brooks’ Theorem and several results on vertex arboricity of graphs of bounded maximum degree. We also prove that deciding whether is -partitionable is -complete for every and pairs of non-negative integers such that and . This resolves an open problem of Bonamy et al. (2017). Combined with results of Borodin et al. (2000), Yang and Yuan (2006) and Wu et al. (1996), it also settles the complexity of deciding whether a graph with bounded maximum degree can be partitioned into two subgraphs of prescribed degeneracy.
The problem of bounding the size of a set system under various intersection restrictions has a central place in extremal combinatorics. We investigate the maximum number of a set system can have in this setting. In particular, we show that for any pair of set systems which avoid a cross-intersection of size , the number of disjoint pairs with and is at most . This implies an asymptotically best possible upper bound on the number of disjoint pairs in a single -avoiding family . We also study this problem when , are both -uniform, and show that it is closely related to the problem of determining the maximum of the product when and avoid a cross-intersection of size , and .
The partition number of a simplicial complex is the minimum integer such that for each partition of at least one of the sets is in . A complex is -unavoidable if . Simplicial complexes with small are important for applications of the “constraint method” (Blagojević et al., 2014) and serve as an input for the “index inequalities” (Jojić et al., 2018), such as (1.1). We introduce a “threshold characteristic” of (Section 3) and define a fractional (linear programming) relaxation of (Section 4), which allows us to systematically generate interesting examples of -unavoidable complexes and pave the way for new results of Van Kampen–Flores–Tverberg type.
Given an ordered triple of positive integers , where , does there exist a matrix of size with exactly invertible submatrices of size ? Such a matrix is called an -matrix. This question is a stronger version of an open problem in matroid theory raised by Dominic Welsh. In this paper, we prove that an -matrix exists when the corank satisfies , unless . Furthermore, we show that an -matrix exists when the rank is large relative to the corank .
In this paper, we study product-free subsets of the free semigroup over a finite alphabet . We prove that the maximum density of a product-free subset of the free semigroup over , with respect to the natural measure that assigns a weight of to each word of length , is precisely .
We introduce the concept of , generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez (2008). We say that a class of graphs admits if there exist functions and such that for all , every graph can be vertex colored with at most colors such that the union of any color classes induces a subgraph of rank-width at most . Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class of bounded expansion and every positive integer , the class of th powers of graphs from admits low rank-width colorings. On the negative side, we show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. As interesting side properties, we prove that every hereditary graph class admitting low rank-width colorings has the Erdős–Hajnal property and is -bounded.
The Combinatorial Nullstellensatz is one of the most powerful algebraic tools in combinatorics. The aim of this paper is to prove an extension of the Combinatorial Nullstellensatz for multisets due to Kós–Rónyai. Our generalization gives an improvement on the size of sets chosen in the statement of Combinatorial Nullstellensatz for some polynomials.
Binomial edge ideals are a noteworthy class of binomial ideals that can be associated with graphs, generalizing the ideals of 2-minors. For bipartite graphs we prove the converse of Hartshorne’s Connectedness Theorem, according to which if an ideal is Cohen–Macaulay, then its dual graph is connected. This allows us to classify Cohen–Macaulay binomial edge ideals of bipartite graphs, giving an explicit and recursive construction in graph-theoretical terms. This result represents a binomial analogue of the celebrated characterization of (monomial) edge ideals of bipartite graphs due to Herzog and Hibi (2005).
We present an algorithm that, given a channel, determines if there is a distance for it such that the maximum likelihood decoder coincides with the minimum distance decoder. We also show that any metric, up to a decoding equivalence, can be isometrically embedded into the hypercube with the Hamming metric, and thus, in terms of decoding, the Hamming metric is universal.
A graph is if all its maximal independent sets are of the same size (Plummer, 1970). A well-covered graph is 1- if the deletion of any one vertex leaves a graph, which is well-covered as well (Staples, 1975). A graph belongs to class if every pairwise disjoint independent sets in are included in pairwise disjoint maximum independent sets (Staples, 1975). Clearly, is the family of all well-covered graphs. It turns out that if and only if it is a 1-well-covered graph without isolated vertices. We show that deleting a shedding vertex does not change the maximum size of a maximal independent set including a given independent set. Specifically, for well-covered graphs, it means that the vertex is shedding if and only if is well-covered. In addition, we provide new characterizations of 1-well-covered graphs.
Let . The daisy cube is introduced as the subgraph of induced by the union of the intervals over all . Daisy cubes are partial cubes that include Fibonacci cubes, Lucas cubes, and bipartite wheels. If is a vertex of a graph , then the distance cube polynomial is introduced as the bivariate polynomial that counts the number of induced subgraphs isomorphic to at a given distance from the vertex . It is proved that if is a daisy cube, then , where is the previously investigated cube polynomial of . It is also proved that if is a daisy cube, then holds for every vertex in .
We consider asymptotics of set partition pattern avoidance in the sense of Klazar. Our main result derives the asymptotics of the number of set partitions avoiding a given set partition within an exponential factor, which leads to a classification of possible growth rates of set partition pattern classes. We further define a notion of permutation-tuple avoidance, which generalizes notions of Aldred et al. and the usual permutation pattern setting, and similarly determine the number of permutation-tuples avoiding a given tuple to within an exponential factor. We note a seeming connection to previous results on hereditary properties of labelled graphs, prompting the question of if there is a generalization to ordered graphs.
Two families, and , of subsets of are cross -intersecting if for every and , and intersect in at least elements. For a real number and a family the product measure is defined as the sum of over all . For every non-negative integer , and for large enough , we determine, for any satisfying , the maximum possible value of for cross -intersecting families and . In this paper we prove a stronger stability result which yields the above result.
DP-coloring as a generalization of list coloring was introduced by Dvořák and Postle in 2017, who proved that every planar graph without cycles from 4 to 8 is 3-choosable, which was conjectured by Borodin et al. in 2007. In this paper, we prove that every planar graph without adjacent cycles of length at most 8 is 3-choosable, which extends this result of Dvořák and Postle.
A graph is - if there exists an assignment of -element subsets of to vertices of such that sets assigned to adjacent vertices are disjoint. We show that every planar graph without cycles of length 4 or 5 is -colorable, a weakening of recently disproved Steinberg’s conjecture. In particular, each such graph with vertices has an independent set of size at least .
Let and be fixed. Let . The of , denoted by , is the maximum number of pairwise disjoint sets in . is if it does not contain sets with union of size at most and empty intersection. In this paper, we give a lower bound and an upper bound for the maximum size of a -cluster-free family with a matching number at least . In particular, our result of the case settles a conjecture of Mammoliti and Britz. We also introduce a Turán problem in hypergraphs that allows multiple edges, which may be of independent interest.