Zobrazeno 1 - 10
of 337
pro vyhledávání: '"Szabó, Tibor"'
We investigate subsets with small sumset in arbitrary abelian groups. For an abelian group $G$ and an $n$-element subset $Y \subseteq G$ we show that if $m \ll s^2/(\log n)^2$, then the number of subsets $A \subseteq Y$ with $|A| = s$ and $|A + A| \l
Externí odkaz:
http://arxiv.org/abs/2407.04492
Consider the Erd\H{o}s-R\'enyi random graph process $\{G_m\}_{m \ge 0}$ in which we start with an empty graph $G_0$ on the vertex set $[n]$, and in each step form $G_i$ from $G_{i-1}$ by adding one new edge chosen uniformly at random. Resolving a con
Externí odkaz:
http://arxiv.org/abs/2401.10803
Given a fixed graph $H$ and an $n$-vertex graph $G$, the $H$-bootstrap percolation process on $G$ is defined to be the sequence of graphs $G_i$, $i\geq 0$ which starts with $G_0:=G$ and in which $G_{i+1}$ is obtained from $G_i$ by adding every edge t
Externí odkaz:
http://arxiv.org/abs/2308.00498
We study multigraphs whose edge-sets are the union of three perfect matchings, $M_1$, $M_2$, and $M_3$. Given such a graph $G$ and any $a_1,a_2,a_3\in \mathbb{N}$ with $a_1+a_2+a_3\leq n-2$, we show there exists a matching $M$ of $G$ with $|M\cap M_i
Externí odkaz:
http://arxiv.org/abs/2212.03100
We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of Erd\H{o}s. Most notably, we improve the upper bounds on the Ramsey multiplicity of $K_4$ and $K_5$ and settle the minimum
Externí odkaz:
http://arxiv.org/abs/2206.04036
Autor:
Haxell, Penny, Szabó, Tibor
In the max-min allocation problem a set $P$ of players are to be allocated disjoint subsets of a set $R$ of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa
Externí odkaz:
http://arxiv.org/abs/2202.01143
In 1985, Mader conjectured that for every acyclic digraph $F$ there exists $K=K(F)$ such that every digraph $D$ with minimum out-degree at least $K$ contains a subdivision of $F$. This conjecture remains widely open, even for digraphs $F$ on five ver
Externí odkaz:
http://arxiv.org/abs/2008.13224
We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph $F$, denote by $\text{mader}_{\vec{\chi}}(F)$ the smallest integer $k$ such that every $k$-dichromatic digraph contains a su
Externí odkaz:
http://arxiv.org/abs/2008.09888
A well-known conjecture, often attributed to Ryser, states that the cover number of an $r$-partite $r$-uniform hypergraph is at most $r - 1$ times larger than its matching number. Despite considerable effort, particularly in the intersecting case, th
Externí odkaz:
http://arxiv.org/abs/2001.04132
A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen and Wood proved that every digraph has a majority 4-coloring and conject
Externí odkaz:
http://arxiv.org/abs/1911.01954