Charles University

output

19922026

most citedObservation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC

10.9k citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing 2016 · math.COShow all

15 papers · 2 filters

math.CO2016★ 31 cited

Defective colouring of graphs excluding a subgraph or minor

Patrice Ossona de Mendez, Sang-il Oum, David R. Wood

Archdeacon (1987) proved that graphs embeddable on a fixed surface can be $3$ -coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, O…

math.CO2016★ 12 cited

Canonical Functions: a proof via topological dynamics

Manuel Bodirsky, Michael Pinsker

Canonical functions are a powerful concept with numerous applications in the study of groups, monoids, and clones on countable structures with Ramsey-type properties. In this short…

math.CO2016

Pach's selection theorem does not admit a topological extension

Imre Bárány, Roy Meshulam, Eran Nevo +1

Let $U_{1}, \dots, U_{d + 1}$ be $n$ -element sets in $R^{d}$ and let $⟨ u_{1}, \dots, u_{d + 1} ⟩$ denote the convex hull of points $u_{i}$ in $U_{i}$ (for all $i$ ) which is a (possibly…

math.CO2016

Drawing graphs using a small number of obstacles

Martin Balko, Josef Cibulka, Pavel Valtr

An obstacle representation of a graph $G$ is a set of points in the plane representing the vertices of $G$ , together with a set of polygonal obstacles such that two vertices of $G$ …

math.CO2016★ 4 cited

Simple realizability of complete abstract topological graphs simplified

Jan Kynčl

An abstract topological graph (briefly an AT-graph) is a pair $A = (G, X)$ where $G = (V, E)$ is a graph and $X \subseteq (2 E)$ is a set of pairs of its edges…

math.CO2016★ 11 cited

Cops and Robbers on Intersection Graphs

Tomáš Gavenčiak, Przemysław Gordinowicz, Vít Jelínek +2

The cop number of a graph $G$ is the smallest $k$ such that $k$ cops win the game of cops and robber on $G$ . We investigate the maximum cop number of geometric intersection graphs,…

math.CO2016★ 11 cited

Trimming and gluing Gray codes

Petr Gregor, Torsten Mütze

We consider the algorithmic problem of generating each subset of $[n] := {1, 2, \dots, n}$ whose size is in some interval $[k, l]$ , $0 \leq k \leq l \leq n$ , exactly once (cyclically) by…

math.CO2016★ 7 cited

A Ramsey Class for Steiner Systems

Vindya Bhat, Jaroslav Nešetřil, Christian Reiher +1

We construct a Ramsey class whose objects are Steiner systems. In contrast to the situation with general $r$ -uniform hypergraphs, it turns out that simply putting linear orders on…

math.CO2016

Triangle-free planar graphs with the smallest independence number

Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1

Steinberg and Tovey proved that every n-vertex planar triangle-free graph has an independent set of size at least (n+1)/3, and described an infinite class of tight examples. We sho…

math.CO2016★ 53 cited

All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)

Jan Hubička, Jaroslav Nešetřil

We prove the Ramsey property for classes of ordered structures with closures and given local properties. This generalises earlier results: the Nešetřil-Rödl Theorem, the Ramsey pro…

math.CO2016★ 10 cited

On ordered Ramsey numbers of bounded-degree graphs

Martin Balko, Vít Jelínek, Pavel Valtr

An ordered graph is a pair $G = (G, ≺)$ where $G$ is a graph and $≺$ is a total ordering of its vertices. The ordered Ramsey number $R (G)$ is th…

math.CO2016★ 8 cited

On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor

Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz +2

The generalised colouring numbers $col_{r} (G)$ and $wcol_{r} (G)$ were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have sin…

math.CO2016★ 8 cited

Near equipartitions of colored point sets

Andreas F. Holmsen, Jan Kynčl, Claudiu Valculescu

Suppose that $nk$ points in general position in the plane are colored red and blue, with at least $n$ points of each color. We show that then there exist $n$ pairwise disjoint conv…

math.CO2016

On Betti numbers of flag complexes with forbidden induced subgraphs

Karim Adiprasito, Eran Nevo, Martin Tancer

We analyze the asymptotic extremal growth rate of the Betti numbers of clique complexes of graphs on n vertices not containing a fixed forbidden induced subgraph H. In particular,…

math.CO2016★ 1 cited

Treeable Graphings Are Local Limits of Finite Graphs

Lucas Hosseini, Patrice Ossona de Mendez

Let $G$ be a graphing, that is a Borel graph defined by $d$ measure preserving involutions. We prove that if $G$ is {\em treeable} then it arises as the local limit…