BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vít Jelínek

Vít Jelínek appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsComputational GeometryComputational ComplexityData Structures and Algorithmsmath.MGmath.NT

Catalog footprint

What is connected

16works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

16 published item(s)

preprint2023arXiv

Structure of betweenness uniform graphs with low values of betweenness centrality

This work deals with undirected graphs that have the same betweenness centrality for each vertex, so-called betweenness uniform graphs (or BUGs). The class of these graphs is not trivial and its classification is still an open problem. Recently, Gago, Coroničová-Hurajová and Madaras conjectured that for every rational $α\ge 3/4$ there exists a BUG having betweenness centrality~$α$. We disprove this conjecture, and provide an alternative view of the structure of betweenness-uniform graphs from the point of view of their complement. This allows us to characterise all the BUGs with betweennes centrality at most 9/10, and show that their betweenness centrality is equal to $\frac{\ell}{\ell+1}$ for some integer $\ell\le 9$. We conjecture that this characterization extends to all the BUGs with betweenness centrality smaller than~1.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes

Permutation Pattern Matching (PPM) is the problem of deciding for a given pair of permutations P and T whether the pattern P is contained in the text T. Bose, Buss and Lubiw showed that PPM is NP-complete. In view of this result, it is natural to ask how the situation changes when we restrict the pattern P to a fixed permutation class C; this is known as the C-Pattern PPM problem. Grid classes are special kind of permutation classes, consisting of permutations admitting a grid-like decomposition into simpler building blocks. Of particular interest are the so-called monotone grid classes, in which each building block is a monotone sequence. Recently, it has been discovered that grid classes, especially the monotone ones, play a fundamental role in the understanding of the structure of general permutation classes. This motivates us to study the hardness of C-Pattern PPM for a (monotone) grid class C. We provide a complexity dichotomy for C-Pattern PPM when C is taken to be a monotone grid class. Specifically, we show that the problem is polynomial-time solvable if a certain graph associated with C, called the cell graph, is a forest, and it is NP-complete otherwise. We further generalize our results to grid classes whose blocks belong to classes of bounded grid-width. We show that the C-Pattern PPM for such a grid class C is polynomial-time solvable if the cell graph of C avoids a cycle or a certain special type of path, and it is NP-complete otherwise.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Hardness of Permutation Pattern Matching

Permutation Pattern Matching (or PPM) is a decision problem whose input is a pair of permutations $π$ and $τ$, represented as sequences of integers, and the task is to determine whether $τ$ contains a subsequence order-isomorphic to $π$. Bose, Buss and Lubiw proved that PPM is NP-complete on general inputs. We show that PPM is NP-complete even when $π$ has no decreasing subsequence of length 3 and $τ$ has no decreasing subsequence of length 4. This provides the first known example of PPM being hard when one or both of $π$ and $σ$ are restricted to a proper hereditary class of permutations. This hardness result is tight in the sense that PPM is known to be polynomial when both $π$ and $τ$ avoid a decreasing subsequence of length 3, as well as when $π$ avoids a decreasing subsequence of length 2. The result is also tight in another sense: we will show that for any hereditary proper subclass C of the class of permutations avoiding a decreasing sequence of length 3, there is a polynomial algorithm solving PPM instances where $π$ is from C and $τ$ is arbitrary. We also obtain analogous hardness and tractability results for the class of so-called skew-merged patterns. From these results, we deduce a complexity dichotomy for the PPM problem restricted to $π$ belonging to $Av(ρ)$, where $Av(ρ)$ denotes the class of permutations avoiding a permutation $ρ$. Specifically, we show that the problem is polynomial when $ρ$ is in the set {1, 12, 21, 132, 213, 231, 312}, and it is NP-complete for any other $ρ$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Beer index of convexity and its variants

Let $S$ be a subset of $\mathbb{R}^d$ with finite positive Lebesgue measure. The Beer index of convexity $\operatorname{b}(S)$ of $S$ is the probability that two points of $S$ chosen uniformly independently at random see each other in $S$. The convexity ratio $\operatorname{c}(S)$ of $S$ is the Lebesgue measure of the largest convex subset of $S$ divided by the Lebesgue measure of $S$. We investigate the relationship between these two natural measures of convexity. We show that every set $S\subseteq\mathbb{R}^2$ with simply connected components satisfies $\operatorname{b}(S)\leqα\operatorname{c}(S)$ for an absolute constant $α$, provided $\operatorname{b}(S)$ is defined. This implies an affirmative answer to the conjecture of Cabello et al. that this estimate holds for simple polygons. We also consider higher-order generalizations of $\operatorname{b}(S)$. For $1\leq k\leq d$, the $k$-index of convexity $\operatorname{b}_k(S)$ of a set $S\subseteq\mathbb{R}^d$ is the probability that the convex hull of a $(k+1)$-tuple of points chosen uniformly independently at random from $S$ is contained in $S$. We show that for every $d\geq 2$ there is a constant $β(d)>0$ such that every set $S\subseteq\mathbb{R}^d$ satisfies $\operatorname{b}_d(S)\leqβ\operatorname{c}(S)$, provided $\operatorname{b}_d(S)$ exists. We provide an almost matching lower bound by showing that there is a constant $γ(d)>0$ such that for every $\varepsilon\in(0,1)$ there is a set $S\subseteq\mathbb{R}^d$ of Lebesgue measure $1$ satisfying $\operatorname{c}(S)\leq\varepsilon$ and $\operatorname{b}_d(S)\geqγ\frac{\varepsilon}{\log_2{1/\varepsilon}}\geqγ\frac{\operatorname{c}(S)}{\log_2{1/\operatorname{c}(S)}}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the hardness of switching to a small number of edges

Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other one by a sequence of switches. Jelínková et al. [DMTCS 13, no. 2, 2011] presented a proof that it is NP-complete to decide if the input graph can be switched to contain at most a given number of edges. There turns out to be a flaw in their proof. We present a correct proof. Furthermore, we prove that the problem remains NP-complete even when restricted to graphs whose density is bounded from above by an arbitrary fixed constant. This partially answers a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014].

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Catalan pairs and Fishburn triples

Disanto, Ferrari, Pinzani and Rinaldi have introduced the concept of 'Catalan pair', which is a pair of partial orders (S,R) satisfying certain axioms. They have shown that Catalan pairs provide a natural description of objects belonging to several classes enumerated by Catalan numbers. In this paper, we first introduce another axiomatic structure (T,R), which we call the 'Catalan pair of type 2', which describes certain Catalan objects that do not seem to have an easy interpretation in terms of the original Catalan pairs. We then introduce 'Fishburn triples', which are relational structures obtained as a direct common generalization of the two types of Catalan pairs. Fishburn triples encode, in a natural way, the structure of objects enumerated by the Fishburn numbers, such as interval orders or Fishburn matrices. This connection between Catalan objects and Fishburn objects allows us to associate known statistics on Catalan objects with analogous statistics of Fishburn objects. As our main result, we then show that several known equidistribution results on Catalan statistics can be generalized to analogous results for Fishburn statistics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Planar Embeddings with Small and Uniform Faces

Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and UNIFORMFACES of embedding a given biconnected multi-graph such that the largest face is as small as possible and such that all faces have the same size, respectively. We prove a complexity dichotomy for MINMAXFACE and show that deciding whether the maximum is at most $k$ is polynomial-time solvable for $k \leq 4$ and NP-complete for $k \geq 5$. Further, we give a 6-approximation for minimizing the maximum face in a planar embedding. For UNIFORMFACES, we show that the problem is NP-complete for odd $k \geq 7$ and even $k \geq 10$. Moreover, we characterize the biconnected planar multi-graphs admitting 3- and 4-uniform embeddings (in a $k$-uniform embedding all faces have size $k$) and give an efficient algorithm for testing the existence of a 6-uniform embedding.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Multiple Pattern Avoiding Set Partitions

We study classes of set partitions determined by the avoidance of multiple patterns, applying a natural notion of partition containment that has been introduced by Sagan. We say that two sets S and T of patterns are equivalent if for each n, the number of partitions of size n avoiding all the members of S is the same as the number of those that avoid all the members of T. Our goal is to classify the equivalence classes among two-element pattern sets of several general types. First, we focus on pairs of patterns {σ,τ}, where σ is a pattern of size three with at least two distinct symbols and τ is an arbitrary pattern of size k that avoids σ. We show that pattern-pairs of this type determine a small number of equivalence classes; in particular, the classes have on average exponential size in k. We provide a (sub-exponential) upper bound for the number of equivalence classes, and provide an explicit formula for the generating function of all such avoidance classes, showing that in all cases this generating function is rational. Next, we study partitions avoiding a pair of patterns of the form {1212,τ}, where τ is an arbitrary pattern. Note that partitions avoiding 1212 are exactly the non-crossing partitions. We provide several general equivalence criteria for pattern pairs of this type, and show that these criteria account for all the equivalences observed when τ has size at most six. In the last part of the paper, we perform a full classification of the equivalence classes of all the pairs {σ,τ}, where σ and τ have size four.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On q-Series Identities Related to Interval Orders

We prove several power series identities involving the refined generating function of interval orders, as well as the refined generating function of the self-dual interval orders. These identities may be expressed as $\sum_{n\ge 0}(1/p;1/q)_n= \sum_{n\ge 0} pq^n(p;q)_n(q;q)_n$ and $\sum_{n\ge 0} (-1)^n(1/p;1/q)_n= \sum_{n\ge 0} pq^n(p;q)_n(-q;q)_n =\sum_{n\ge 0} (q/p)^n(p;q^2)_n$, where the equalities apply to the (purely formal) power series expansions of the above expressions at $p=q=1$, as well as at other suitable roots of unity.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Splittings and Ramsey Properties of Permutation Classes

We say that a permutation p is 'merged' from permutations q and r, if we can color the elements of p red and blue so that the red elements are order-isomorphic to q and the blue ones to r. A 'permutation class' is a set of permutations closed under taking subpermutations. A permutation class C is 'splittable' if it has two proper subclasses A and B such that every element of C can be obtained by merging an element of A with an element of B. Several recent papers use splittability as a tool in deriving enumerative results for specific permutation classes. The goal of this paper is to study splittability systematically. As our main results, we show that if q is a sum-decomposable permutation of order at least four, then the class Av(q) of all q-avoiding permutations is splittable, while if q is a simple permutation, then Av(q) is unsplittable. We also show that there is a close connection between splittings of certain permutation classes and colorings of circle graphs of bounded clique size. Indeed, our splittability results can be interpreted as a generalization of a theorem of Gyárfás stating that circle graphs of bounded clique size have bounded chromatic number.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs

A partially embedded graph (or PEG) is a triple (G,H,\H), where G is a graph, H is a subgraph of G, and \H is a planar embedding of H. We say that a PEG (G,H,\H) is planar if the graph G has a planar embedding that extends the embedding \H. We introduce a containment relation of PEGs analogous to graph minor containment, and characterize the minimal non-planar PEGs with respect to this relation. We show that all the minimal non-planar PEGs except for finitely many belong to a single easily recognizable and explicitly described infinite family. We also describe a more complicated containment relation which only has a finite number of minimal non-planar PEGs. Furthermore, by extending an existing planarity test for PEGs, we obtain a polynomial-time algorithm which, for a given PEG, either produces a planar embedding or identifies an obstruction.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B_k-VPG. We show here that for every fixed k, B_k-VPG is a proper subset of B_{k+1}-VPG and that recognition of graphs from B_k-VPG is NP-complete even when the input graph is given by a B_{k+1}-VPG representation. We also show that the class B_k-VPG (for k>0) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Counting Self-Dual Interval Orders

In this paper, we present a new method to derive formulas for the generating functions of interval orders, counted with respect to their size, magnitude, and number of minimal and maximal elements. Our method allows us not only to generalize previous results on refined enumeration of general interval orders, but also to enumerate self-dual interval orders with respect to analogous statistics. Using the newly derived generating function formulas, we are able to prove a bijective relationship between self-dual interval orders and upper-triangular matrices with no zero rows. Previously, a similar bijective relationship has been established between general interval orders and upper-triangular matrices with no zero rows and columns.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns

We prove that the Stanley-Wilf limit of any layered permutation pattern of length $\ell$ is at most $4\ell^2$, and that the Stanley-Wilf limit of the pattern 1324 is at most 16. These bounds follow from a more general result showing that a permutation avoiding a pattern of a special form is a merge of two permutations, each of which avoids a smaller pattern. If the conjecture is true that the maximum Stanley-Wilf limit for patterns of length $\ell$ is attained by a layered pattern then this implies an upper bound of $4\ell^2$ for the Stanley-Wilf limit of any pattern of length $\ell$. We also conjecture that, for any $k\ge 0$, the set of 1324-avoiding permutations with $k$ inversions contains at least as many permutations of length $n+1$ as those of length $n$. We show that if this is true then the Stanley-Wilf limit for 1324 is at most $e^{π\sqrt{2/3}} \simeq 13.001954$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree $Δ$. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most $O(Δ^5)$. In particular, we answer the question of Dujmović et al. [Computational Geometry 38 (3), pp. 194--212 (2007)] whether there is a function $f$ such that plane maximal outerplanar graphs can be drawn using at most $f(Δ)$ slopes.

0 citations0 reviewsNo code linkedOpen access