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

Josef Cibulka

Josef Cibulka appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete Mathematicsmath.COComputational GeometryComputational ComplexityData Structures and Algorithms

Catalog footprint

What is connected

11works
5topics
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

11 published item(s)

preprint2019arXiv

Ramsey numbers of ordered graphs

An ordered graph is a pair $\mathcal{G}=(G,\prec)$ where $G$ is a graph and $\prec$ is a total ordering of its vertices. The ordered Ramsey number $\overline{R}(\mathcal{G})$ is the minimum number $N$ such that every ordered complete graph with $N$ vertices and with edges colored by two colors contains a monochromatic copy of $\mathcal{G}$. In contrast with the case of unordered graphs, we show that there are arbitrarily large ordered matchings $\mathcal{M}_n$ on $n$ vertices for which $\overline{R}(\mathcal{M}_n)$ is superpolynomial in $n$. This implies that ordered Ramsey numbers of the same graph can grow superpolynomially in the size of the graph in one ordering and remain linear in another ordering. We also prove that the ordered Ramsey number $\overline{R}(\mathcal{G})$ is polynomial in the number of vertices of $\mathcal{G}$ if the bandwidth of $\mathcal{G}$ is constant or if $\mathcal{G}$ is an ordered graph of constant degeneracy and constant interval chromatic number. The first result gives a positive answer to a question of Conlon, Fox, Lee, and Sudakov. For a few special classes of ordered paths, stars or matchings, we give asymptotically tight bounds on their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly. This result implies exact formulas for geometric Ramsey numbers of cycles introduced by Károlyi, Pach, Tóth, and Valtr.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Three-monotone interpolation

A function $f\colon\mathbb R\to\mathbb R$ is called \emph{$k$-monotone} if it is $(k-2)$-times differentiable and its $(k-2)$nd derivative is convex. A point set $P\subset\mathbb R^2$ is \emph{$k$-monotone interpolable} if it lies on a graph of a $k$-monotone function. These notions have been studied in analysis, approximation theory etc. since the 1940s. We show that 3-monotone interpolability is very non-local: we exhibit an arbitrarily large finite $P$ for which every proper subset is $3$-monotone interpolable but $P$ itself is not. On the other hand, we prove a Ramsey-type result: for every $n$ there exists $N$ such that every $N$-point $P$ with distinct $x$-coordinates contains an $n$-point $Q$ such that $Q$ or its vertical mirror reflection are $3$-monotone interpolable. The analogs for $k$-monotone interpolability with $k=1$ and $k=2$ are classical theorems of Erdős and Szekeres, while the cases with $k\ge4$ remain open. We also investigate the computational complexity of deciding $3$-monotone interpolability of a given point set. Using a known characterization, this decision problem can be stated as an instance of polynomial optimization and reformulated as a semidefinite program. We exhibit an example for which this semidefinite program has only doubly exponentially large feasible solutions, and thus known algorithms cannot solve it in polynomial time. While such phenomena have been well known for semidefinite programming in general, ours seems to be the first such example in polynomial optimization, and it involves only univariate quadratic polynomials.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maximum size of reverse-free sets of permutations

Two words have a reverse if they have the same pair of distinct letters on the same pair of positions, but in reversed order. A set of words no two of which have a reverse is said to be reverse-free. Let F(n,k) be the maximum size of a reverse-free set of words from [n]^k where no letter repeats within a word. We show the following lower and upper bounds in the case n >= k: F(n,k) \in n^k k^{-k/2 + O(k/log k)}. As a consequence of the lower bound, a set of n-permutations each two having a reverse has size at most n^{n/2 + O(n/log n)}.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Geometric Ramsey Number of Outerplanar Graphs

We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on $2n$ vertices are bounded by $O(n^{3})$ and $O(n^{10})$, in the convex and general case, respectively. We then apply similar methods to prove an $n^{O(\log(n))}$ upper bound on the Ramsey number of a path with $n$ ordered vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Graph sharing games: complexity and connectivity

We study the following combinatorial game played by two players, Alice and Bob, which generalizes the Pizza game considered by Brown, Winkler and others. Given a connected graph G with nonnegative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice's. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that if rules (T) and/or (R) are required then for every epsilon > 0 and for every positive integer k there is a k-connected graph G for which Bob has a strategy to obtain (1-epsilon) of the total weight of the vertices. This contrasts with the original Pizza game played on a cycle, where Alice is known to have a strategy to obtain 4/9 of the total weight. We show that the problem of deciding whether Alice has a winning strategy (i.e., a strategy to obtain more than half of the total weight) is PSPACE-complete if condition (R) or both conditions (T) and (R) are required. We also consider a game played on connected graphs (without weights) where the first player who violates condition (T) or (R) loses the game. We show that deciding who has the winning strategy is PSPACE-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

The VC-dimension of a family P of n-permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. Let r_k(n) be the maximum size of a set of n-permutations with VC-dimension k. Raz showed that r_2(n) grows exponentially in n. We show that r_3(n)=2^Theta(n log(alpha(n))) and for every s >= 4, we have almost tight upper and lower bounds of the form 2^{n poly(alpha(n))}. We also study the maximum number p_k(n) of 1-entries in an n x n (0,1)-matrix with no (k+1)-tuple of columns containing all (k+1)-permutation matrices. We determine that p_3(n) = Theta(n alpha(n)) and that p_s(n) can be bounded by functions of the form n 2^poly(alpha(n)) for every fixed s >= 4. We also show that for every positive s there is a slowly growing function zeta_s(m) (of the form 2^poly(alpha(m)) for every fixed s >= 5) satisfying the following. For all positive integers n and B and every n x n (0,1)-matrix M with zeta_s(n)Bn 1-entries, the rows of M can be partitioned into s intervals so that at least B columns contain at least B 1-entries in each of the intervals.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

A set S of n points is 2-color universal for a graph G on n vertices if for every proper 2-coloring of G and for every 2-coloring of S with the same sizes of color classes as G has, G is straight-line embeddable on S. We show that the so-called double chain is 2-color universal for paths if each of the two chains contains at least one fifth of all the points, but not if one of the chains is more than approximately 28 times longer than the other. A 2-coloring of G is equitable if the sizes of the color classes differ by at most 1. A bipartite graph is equitable if it admits an equitable proper coloring. We study the case when S is the double-chain with chain sizes differing by at most 1 and G is an equitable bipartite graph. We prove that this S is not 2-color universal if G is not a forest of caterpillars and that it is 2-color universal for equitable caterpillars with at most one half non-leaf vertices. We also show that if this S is equitably 2-colored, then equitably properly 2-colored forests of stars can be embedded on it.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Polynomial-time sortable stacks of burnt pancakes

Pancake flipping, a famous open problem in computer science, can be formalised as the problem of sorting a permutation of positive integers using as few prefix reversals as possible. In that context, a prefix reversal of length k reverses the order of the first k elements of the permutation. The burnt variant of pancake flipping involves permutations of signed integers, and reversals in that case not only reverse the order of elements but also invert their signs. Although three decades have now passed since the first works on these problems, neither their computational complexity nor the maximal number of prefix reversals needed to sort a permutation is yet known. In this work, we prove a new lower bound for sorting burnt pancakes, and show that an important class of permutations, known as "simple permutations", can be optimally sorted in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Average number of flips in pancake sorting

We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We present an algorithm with the average number of flips, needed to sort a stack of n burnt pancakes, equal to 7n/4+O(1) and a randomized algorithm for the unburnt version with at most 17n/12+O(1) flips on average. In addition, we show that in the burnt version, the average number of flips of any algorithm is at least n+Ω(n/log n) and conjecture that some algorithm can reach n+Θ(n/log n). We also slightly increase the lower bound on g(n), the minimum number of flips needed to sort the worst stack of n burnt pancakes. This bound, together with the upper bound found by Heydari and Sudborough in 1997, gives the exact number of flips to sort the previously conjectured worst stack -I_n for n=3 mod 4 and n>=15. Finally we present exact values of f(n) up to n=19 and of g(n) up to n=17 and disprove a conjecture of Cohen and Blum by showing that the burnt stack -I_{15} is not the worst one for n=15.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Solution of Peter Winkler's Pizza Problem

Bob cuts a pizza into slices of not necessarily equal size and shares it with Alice by alternately taking turns. One slice is taken in each turn. The first turn is Alice's. She may choose any of the slices. In all other turns only those slices can be chosen that have a neighbor slice already eaten. We prove a conjecture of Peter Winkler by showing that Alice has a strategy for obtaining 4/9 of the pizza. This is best possible, that is, there is a cutting and a strategy for Bob to get 5/9 of the pizza. We also give a characterization of Alice's best possible gain depending on the number of slices. For a given cutting of the pizza, we describe a linear time algorithm that computes Alice's strategy gaining at least 4/9 of the pizza and another algorithm that computes the optimal strategy for both players in any possible position of the game in quadratic time. We distinguish two types of turns, shifts and jumps. We prove that Alice can gain 4/9, 7/16 and 1/3 of the pizza if she is allowed to make at most two jumps, at most one jump and no jump, respectively, and the three constants are the best possible.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Untangling polygons and graphs

Untangling is a process in which some vertices of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C_n while keeping at least Ω(n^{2/3}) vertices fixed. For any graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound O((n log n)^{2/3}) for all 3-vertex-connected planar graphs.

0 citations0 reviewsNo code linkedOpen access