0
0.0

Jun 29, 2018
06/18

by
Andrii Arman; Vojtěch Rödl

texts

######
eye 0

######
favorite 0

######
comment 0

In this note we consider a Ramsey type result for partially ordered sets. In particular, we give an alternative short proof of a theorem for a posets with multiple linear extensions recently obtained by Solecki and Zhao.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1608.05290

27
27

Sep 22, 2013
09/13

by
Vojtěch Rödl; Mathias Schacht

texts

######
eye 27

######
favorite 0

######
comment 0

According to Paul Erd\H{o}s [Some notes on Tur\'an's mathematical work, J. Approx. Theory 29 (1980), page 4] it was Paul Tur\'an who "created the area of extremal problems in graph theory". However, without a doubt, Paul Erd\H{o}s popularized extremal combinatorics, by his many contributions to the field, his numerous questions and conjectures, and his influence on discrete mathematicians in Hungary and all over the world. In fact, most of the early contributions in this field can be...

Source: http://arxiv.org/abs/1302.2248v2

0
0.0

Jun 29, 2018
06/18

by
Jaroslav Nešetřil; Vojtěch Rödl

texts

######
eye 0

######
favorite 0

######
comment 0

We prove that finite partial orders with a linear extension form a Ramsey class. Our proof is based on the fact that class of acyclic graphs has the Ramsey property and uses the partite construction.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1608.04662

46
46

Jul 20, 2013
07/13

by
Dhruv Mubayi; Vojtech Rodl

texts

######
eye 46

######
favorite 0

######
comment 0

Let M be a subset of {0, .., n} and F be a family of subsets of an n element set such that the size of A intersection B is in M for every A, B in F. Suppose that l is the maximum number of consecutive integers contained in M and n is sufficiently large. Then we prove that |F| < min {1.622^n 100^l, 2^{n/2+l log^2 n}}. The first bound complements the previous bound of roughly (1.99)^n due to Frankl and the second author which applies even when M={0, 1,.., n} - {n/4}. For small l, the second...

Source: http://arxiv.org/abs/1107.5651v2

0
0.0

Jun 29, 2018
06/18

by
Peter Frankl; Vojtech Rödl; Andrzej Ruciński

texts

######
eye 0

######
favorite 0

######
comment 0

In 1965 Erd\H os conjectured that for all $k\ge2$, $s\ge1$ and $n\ge k(s+1)$, an $n$-vertex $k$-uniform hypergraph $\F$ with $\nu(\F)=s$ cannot have more than \newline $\max\{\binom{sk+k-1}k,\;\binom nk-\binom{n-s}k\}$ edges. It took almost fifty years to prove it for triple systems. In 2012 we proved the conjecture for all $s$ and all $n\ge4(s+1)$. Then {\L}uczak and Mieczkowska (2013) proved the conjecture for sufficiently large $s$ and all $n$. Soon after, Frankl proved it for all $s$. Here...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1609.00530

0
0.0

Jun 29, 2018
06/18

by
Christian Reiher; Vojtěch Rödl; Mathias Schacht

texts

######
eye 0

######
favorite 0

######
comment 0

Extremal problems for $3$-uniform hypergraphs are known to be very difficult and despite considerable effort the progress has been slow. We suggest a more systematic study of extremal problems in the context of quasirandom hypergraphs. We say that a $3$-uniform hypergraph $H=(V,E)$ is weakly $(d,\eta)$-quasirandom if for any subset $U\subseteq V$ the number of hyperedges of $H$ contained in $U$ is in the interval $d\binom{|U|}{3}\pm\eta|V|^3$. We show that for any $\varepsilon>0$ there...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1602.02290

1
1.0

Jun 29, 2018
06/18

by
Vojtěch Rödl; Andrzej Ruciński; Mathias Schacht

texts

######
eye 1

######
favorite 0

######
comment 0

For given integers $k$ and $r$, the Folkman number $f(k;r)$ is the smallest number of vertices in a graph $G$ which contains no clique on $k+1$ vertices, yet for every partition of its edges into $r$ parts, some part contains a clique of order $k$. The existence (finiteness) of Folkman numbers was established by Folkman (1970) for $r=2$ and by Ne\v{s}et\v{r}il and R\"odl (1976) for arbitrary $r$, but these proofs led to very weak upper bounds on $f(k;r)$. Recently, Conlon and Gowers and...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1603.00521

0
0.0

Jun 29, 2018
06/18

by
Yoshiharu Kohayakawa; Vojtěch Rödl; Mathias Schacht

texts

######
eye 0

######
favorite 0

######
comment 0

We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This positively answers a question of Chung and Graham ["Sparse quasi-random graphs", Combinatorica 22 (2002), no. 2, 217-244] for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1602.02291

0
0.0

Jun 29, 2018
06/18

by
Dwight Duffus; Bill Kay; Vojtech Rodl

texts

######
eye 0

######
favorite 0

######
comment 0

An oriented k-uniform hypergraph (a family of ordered k-sets) has the ordering property (or Property O) if for every linear order of the vertex set, there is some edge oriented consistently with the linear order. We find bounds on the minimum number of edges in a hypergraph with Property O.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1608.06621

0
0.0

Jun 29, 2018
06/18

by
Christian Reiher; Vojtěch Rödl; Mathias Schacht

texts

######
eye 0

######
favorite 0

######
comment 0

We investigate extremal problems for quasirandom hypergraphs. We say that a $3$-uniform hypergraph $H=(V,E)$ is $(d,\eta)$-quasirandom if for any subset $X\subseteq V$ and every set of pairs $P\subseteq V\times V$ the number of pairs $(x,(y,z))\in X\times P$ with $\{x,y,z\}$ being a hyperedge of $H$ is in the interval $d|X||P|\pm\eta|V|^3$. We show that for any $\varepsilon>0$ there exists $\eta>0$ such that every sufficiently large $(1/2+\varepsilon,\eta)$-quasirandom hypergraph contains...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1602.02289

0
0.0

Jun 28, 2018
06/18

by
David Conlon; Jacob Fox; Vojtěch Rödl

texts

######
eye 0

######
favorite 0

######
comment 0

We exhibit a family of $3$-uniform hypergraphs with the property that their $2$-colour Ramsey numbers grow polynomially in the number of vertices, while their $4$-colour Ramsey numbers grow exponentially. This is the first example of a class of hypergraphs whose Ramsey numbers show a strong dependence on the number of colours.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1511.00563

0
0.0

Jun 29, 2018
06/18

by
Silvia Messuti; Vojtěch Rödl; Mathias Schacht

texts

######
eye 0

######
favorite 0

######
comment 0

Motivated by a conjecture of Gy\'arf\'as, recently B\"ottcher, Hladk\'y, Piguet, and Taraz showed that every collection $T_1,\dots,T_t$ of trees on $n$ vertices with $\sum_{i=1}^te(T_i)\leq \binom{n}{2}$ and with bounded maximum degree, can be packed into the complete graph on $(1+o(1))n$ vertices. We generalise this result where we relax the restriction of packing families of trees to families of graphs of any given non-trivial minor-closed class of graphs.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1602.06780

56
56

Sep 20, 2013
09/13

by
Ehud Friedgut; Vojtech Rodl; Andrzej Rucinski; Prasad Tetali

texts

######
eye 56

######
favorite 0

######
comment 0

Let $\R$ be the set of all finite graphs $G$ with the Ramsey property that every coloring of the edges of $G$ by two colors yields a monochromatic triangle. In this paper we establish a sharp threshold for random graphs with this property. Let $G(n,p)$ be the random graph on $n$ vertices with edge probability $p$. We prove that there exists a function $\hat c=\hat c(n)$ with $0 0$, as $n$ tends to infinity $$Pr[G(n,(1-\eps)\hat c/\sqrt{n}) \in \R ] \to 0$$ and $$Pr [ G(n,(1+\eps)\hat...

Source: http://arxiv.org/abs/math/0301200v2

0
0.0

Jun 30, 2018
06/18

by
Peter Frankl; János Pach; Christian Reiher; Vojtěch Rödl

texts

######
eye 0

######
favorite 0

######
comment 0

We give a short survey of problems and results on (1) diameter graphs and hypergraphs, and (2) geometric Ramsey theory. We also make some modest contributions to both areas. Extending a well known theorem of Kahn and Kalai which disproved Borsuk's conjecture, we show that for any integer $r\ge 2$, there exist $\varepsilon=\varepsilon(r)>0$ and $d_0=d_0(r)$ with the following property. For every $d\ge d_0$, there is a finite point set $P\subset\mathbb{R}^d$ of diameter $1$ such that no matter...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1702.03707

0
0.0

Jun 29, 2018
06/18

by
Vindya Bhat; Jaroslav Nešetřil; Christian Reiher; Vojtěch Rödl

texts

######
eye 0

######
favorite 0

######
comment 0

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 their sets of vertices is not enough for this purpose: one also has to strengthen the notion of subobjects used from "induced subsystems" to something we call "strongly induced subsystems". Moreover we study the Ramsey properties of other classes of Steiner systems obtained from this class by...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1607.02792

4
4.0

Jun 27, 2018
06/18

by
Andrzej Dudek; Steven La Fleur; Dhruv Mubayi; Vojtech Rodl

texts

######
eye 4

######
favorite 0

######
comment 0

The size-Ramsey number of a graph $G$ is the minimum number of edges in a graph $H$ such that every 2-edge-coloring of $H$ yields a monochromatic copy of $G$. Size-Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size-Ramsey numbers for $k$-uniform hypergraphs. Analogous to the graph case, we consider the size-Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1503.06304

0
0.0

Jun 29, 2018
06/18

by
Christian Reiher; Vojtěch Rödl; Andrzej Ruciński; Mathias Schacht; Endre Szemerédi

texts

######
eye 0

######
favorite 0

######
comment 0

We show that every 3-uniform hypergraph with $n$ vertices and minimum vertex degree at least $(5/9+o(1))\binom{n}2$ contains a tight Hamiltonian cycle. Known lower bound constructions show that this degree condition is asymptotically optimal.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1611.03118

27
27

Sep 23, 2013
09/13

by
Massimo Lauria; Pavel Pudlák; Vojtěch Rödl; Neil Thapen

texts

######
eye 27

######
favorite 0

######
comment 0

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of resolution proofs that $G$ is $c$-Ramsey, for every graph $G$. Our proof makes use of the fact that every Ramsey graph must contain a large subgraph with some of the statistical properties of the random graph.

Source: http://arxiv.org/abs/1303.3166v1

152
152

Jul 20, 2013
07/13

by
Noga Alon; Peter Frankl; Hao Huang; Vojtech Rodl; Andrzej Rucinski; Benny Sudakov

texts

######
eye 152

######
favorite 0

######
comment 0

In this paper we study conditions which guarantee the existence of perfect matchings and perfect fractional matchings in uniform hypergraphs. We reduce this problem to an old conjecture by Erd\H{o}s on estimating the maximum number of edges in a hypergraph when the (fractional) matching number is given, which we are able to solve in some special cases using probabilistic techniques. Based on these results, we obtain some general theorems on the minimum $d$-degree ensuring the existence of...

Source: http://arxiv.org/abs/1107.1219v2

0
0.0

Jun 29, 2018
06/18

by
David Conlon; Domingos Dellamonica; Steven La Fleur; Vojtěch Rödl; Mathias Schacht

texts

######
eye 0

######
favorite 0

######
comment 0

The induced Ramsey number $r_{\mathrm{ind}}(F)$ of a $k$-uniform hypergraph $F$ is the smallest natural number $n$ for which there exists a $k$-uniform hypergraph $G$ on $n$ vertices such that every two-coloring of the edges of $G$ contains an induced monochromatic copy of $F$. We study this function, showing that $r_{\mathrm{ind}}(F)$ is bounded above by a reasonable power of $r(F)$. In particular, our result implies that $r_{\mathrm{ind}}(F) \leq 2^{2^{ct}}$ for any $3$-uniform hypergraph $F$...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1601.01493