Modularity of minor-free graphs
We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, modularity tends to 1 as the number of edges tends to infinity.
Source author record
Michał Lasoń
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
16works
8topics
4close collaborators
Published work
16 publications
preprint2020arXiv
A note on seminormality of cut polytopes
We prove that seminormality of cut polytopes is equivalent to normality. This settles two conjectures regarding seminormality of cut polytopes.
Open access
preprint2020arXiv
On algebraic properties of matroid polytopes
A toric variety is constructed from a lattice polytope. It is common in algebraic combinatorics to carry this way a notion of an algebraic property from the variety to the polytope. From the combinatorial point of view, one of the most interesting constructions of toric varieties comes from the base polytope of a matroid. Matroid base polytopes and independence polytopes are Cohen--Macaulay. We study two natural stronger algebraic properties -- Gorenstein and smooth. We provide a full classifications of matroids whose independence polytope or base polytope is smooth or Gorenstein. The latter answers to a question raised by Herzog and Hibi.
Open access
preprint2016arXiv
Matroid multiple cyclic exchange property
We prove a new exchange property for bases of a matroid that generalizes the multiple symmetric exchange property. For every bases B1,…,Bk of a matroid and a subset A1⊂B1 there exist subsets A2⊂B2,…,Ak⊂Bk such that all sets (Bi∖Ai)∪Ai−1 achieved by a cyclic shift of Ai's by one are bases.
Open access
preprint2015arXiv
K-uniruled sets in affine geometry
The main goal of this thesis is to study K-uniruled sets that appear in affine geometry. At the beginning we discuss the property of K-uniruledness and its equivalent conditions. Then we bound from above the degree of K-uniruledness of the non-properness set of a polynomial map in terms of its degree and degree of K-uniruledness of the domain variety. At the end we show that some sets associated with the set of fixed points of an algebraic group action are K-uniruled.
Open access
preprint2015arXiv
Cox rings of du Val singularities
In this note we introduce Cox rings of singularities and explicitly compute them in the case of du Val singularities Dn,E6,E7 and E8.
Open access
preprint2014arXiv
An extremal problem on crossing vectors
For positive integers w and k, two vectors A and B from Zw are called k-crossing if there are two coordinates i and j such that A[i]−B[i]≥k and B[j]−A[j]≥k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing vectors in Zw? We state a conjecture that the answer is kw−1. We prove the conjecture for w≤3 and provide weaker upper bounds for w≥4. Also, for all k and w, we construct several quite different examples of families of desired size kw−1. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.
Open access
preprint2014arXiv
List coloring of matroids and base exchange properties
A coloring of a matroid is an assignment of colors to the elements of its ground set. We restrict to proper colorings - those for which elements of the same color form an independent set. Seymour proved that a k-colorable matroid is also colorable from any lists of size k. We generalize this theorem to the case when lists have still fixed sizes, but not necessarily equal. For any fixed size of lists assignment ℓ, we prove that, if a matroid is colorable from a particular lists of size ℓ, then it is colorable from any lists of size ℓ. This gives an explicit necessary and sufficient condition for a matroid to be list colorable from any lists of a fixed size. As an application, we show how to use our condition to derive several base exchange properties.
Open access
preprint2014arXiv
Obstacles for splitting multidimensional necklaces
The well-known "necklace splitting theorem" of Alon asserts that every k-colored necklace can be fairly split into q parts using at most t cuts, provided k(q−1)≤t. In a joint paper with Alon et al. we studied a kind of opposite question. Namely, for which values of k and t there is a measurable k-coloring of the real line such that no interval has a fair splitting into 2 parts with at most t cuts? We proved that k>t+2 is a sufficient condition (while k>t is necessary). We generalize this result to Euclidean spaces of arbitrary dimension d, and to arbitrary number of parts q. We prove that if k(q−1)>t+d+q−1, then there is a measurable k-coloring of Rd such that no axis-aligned cube has a fair q-splitting using at most t axis-aligned hyperplane cuts. Our bound is of the same order as a necessary condition k(q−1)>t implied by a theorem of Alon. Moreover for d=1,q=2 we get exactly the result of of Alon et al. Additionally, we prove that if a stronger inequality k(q−1)>dt+d+q−1 is satisfied, then there is a measurable k-coloring of Rd with no axis-aligned cube having a fair q-splitting using at most t arbitrary hyperplane cuts. The proofs are based on the topological Baire category theorem and use algebraic independence over suitably chosen fields.
Open access
preprint2014arXiv
On the relation between Betti numbers of an Arf semigroup and its blowup
In this note we prove the relation between Betti numbers of an Arf semigroup S and its blowup S′ in the case when they have the same multiplicity n. The relation is then βi,s(S′)=βi,s+(i+1)n(S).
Open access
preprint2014arXiv
On the toric ideal of a matroid
Describing minimal generating set of a toric ideal is a well-studied and difficult problem. In 1980 White conjectured that the toric ideal associated to a matroid is equal to the ideal generated by quadratic binomials corresponding to symmetric exchanges. We prove White's conjecture up to saturation, that is that the saturations of both ideals are equal. In the language of algebraic geometry this means that both ideals define the same projective scheme. Additionally we prove the full conjecture for strongly base orderable matroids.
Open access
preprint2014arXiv
Splitting necklaces and measurable colorings of the real line
A (continuous) necklace is simply an interval of the real line colored measurably with some number of colors. A well-known application of the Borsuk-Ulam theorem asserts that every k-colored necklace can be fairly split by at most k cuts (from the resulting pieces one can form two collections, each capturing the same measure of every color). Here we prove that for every k≥1 there is a measurable (k+3)-coloring of the real line such that no interval can be fairly split using at most k cuts. In particular, there is a measurable 4-coloring of the real line in which no two adjacent intervals have the same measure of every color. An analogous problem for the integers was posed by Erdős in 1961 and solved in the affirmative in 1991 by Keränen. Curiously, in the discrete case the desired coloring also uses four colors.
Open access
preprint2014arXiv
Triangle-free geometric intersection graphs with large chromatic number
Several classical constructions illustrate the fact that the chromatic number of a graph can be arbitrarily large compared to its clique number. However, until very recently, no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set X in R2 that is not an axis-aligned rectangle and for any positive integer k produces a family F of sets, each obtained by an independent horizontal and vertical scaling and translation of X, such that no three sets in F pairwise intersect and χ(F)>k. This provides a negative answer to a question of Gyarfas and Lehel for L-shapes. With extra conditions, we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries, and equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.
Open access
preprint2014arXiv
Triangle-free intersection graphs of line segments with large chromatic number
In the 1970s, Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k, we construct a triangle-free family of line segments in the plane with chromatic number greater than k. Our construction disproves a conjecture of Scott that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number.
Open access
preprint2013arXiv
f-vectors implying vertex decomposability
We prove that if a pure simplicial complex of dimension d with n facets has the least possible number of (d-1)-dimensional faces among all complexes with n faces of dimension d, then it is vertex decomposable. This answers a question of J. Herzog and T. Hibi. In fact we prove a generalization of their theorem using combinatorial methods.
Open access
preprint2013arXiv
Indicated coloring of matroids
A coloring of a matroid is proper if elements of the same color form an independent set. For a loopless matroid M, its chromatic number χ(M) is the minimum number of colors that suffices to color properly the ground set E of M. In this note we study a game-theoretic variant of this parameter proposed by Grytczuk. Suppose that in each round of the game Alice indicates an uncolored yet element e of E, then Bob colors it using a color from a fixed set of colors C. The rule Bob has to obey is that it is a proper coloring. The game ends if the whole matroid has been colored or if Bob can not color e using any color of C. Alice wins in the first case, while Bob in the second. The minimum size of the set of colors C for which Alice has a winning strategy is called the indicated chromatic number of M, denoted by χ_i(M). We prove that χ_i(M)=χ(M).
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.