Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Pach, J��nos"'
It is known that any open necklace with beads of $t$ types in which the number of beads of each type is divisible by $k$, can be partitioned by at most $(k-1)t$ cuts into intervals that can be distributed into $k$ collections, each containing the sam
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5fcda5532b4bb5a901785fe3a1433bfb
The {\em disjointness graph} of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph $G$ of any system of segments in the plane is {\em $��$-
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::06c6f41d87bf1ba2b8c1bc2e03e61bd2
We show that every minimum area isosceles triangle containing a given triangle $T$ shares a side and an angle with $T$. This proves a conjecture of Nandakumar motivated by a computational problem. We use our result to deduce that for every triangle $
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ac46d79ac049851234b7eaeb3f33cd58
Autor:
Pach, J��nos, Tomon, Istv��n
An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer $k$, there exists a constant $c_k>0$ such that any ordered graph $G$ on $n$ vertices with the property that neither $G$ nor its complement
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a87eb3e3338a51cdaaef360a0540c6a0
We call a multigraph {\em non-homotopic} if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0c7fae678952bc4a7d5b12cecfe71cbf
Autor:
Pach, J��nos, Tomon, Istv��n
If we want to color $1,2,\ldots,n$ with the property that all 3-term arithmetic progressions are rainbow (that is, their elements receive 3 distinct colors), then, obviously, we need to use at least $n/2$ colors. Surprisingly, much fewer colors suffi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dd80f2d288f46730b3bd40c9e4f1779b
Two subsets $A,B$ of an $n$-element ground set $X$ are said to be \emph{crossing}, if none of the four sets $A\cap B$, $A\setminus B$, $B\setminus A$ and $X\setminus(A\cup B)$ are empty. It was conjectured by Karzanov and Lomonosov forty years ago th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2e76ada332c7904336eef890a7a86d1b
http://arxiv.org/abs/1704.02175
http://arxiv.org/abs/1704.02175
The Vapnik-Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every $n$-vertex graph with bounded VC-dimension contains a clique or an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::17835702e6cbef941223f55634bdaf1a
According to Suk's breakthrough result on the Erdos-Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+O\left({n^{2/3}\log n}\right)}$ points. We
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7ae2e7aec487323fde3ad827470fa98c
Autor:
Fulek, Radoslav, Pach, J��nos
A {\em thrackle} is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of $n$ vertices has at most $1.3984n$ edges. {\em Quasi-thrackles} are
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ebee6f8cf775c3917629cf399c350727