HUN-REN Alfréd Rényi Institute of Mathematics

output

19942026

most citedBrownian distance covariance

857 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 2020 · math.COShow all

14 papers · 2 filters

math.CO2020

On non-adaptive majority problems of large query size

Dániel Gerbner, Máté Vizer

We are given $n$ balls and an unknown coloring of them with two colors. Our goal is to find a ball that belongs to the larger color class, or show that the color classes have the s…

math.CO2020

On Turán numbers of the complete $4$ -graphs

Alexander Sidorenko

The Turán number $T (n, α + 1, r)$ is the minimum number of edges in an $n$ -vertex $r$ -graph whose independence number does not exceed $α$ . For each $r \geq 2$ , there exists $t_{*} (r)$ suc…

math.CO2020★ 2 cited

Computing the covering radius of a polytope with an application to lonely runners

Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi +1

We are concerned with the computational problem of determining the covering radius of a rational polytope. This parameter is defined as the minimal dilation factor that is needed f…

math.CO2020

Flows on measurable spaces

Laszlo Lovasz

The theory of graph limits is only understood to any nontrivial degree in the cases of dense graphs and of bounded degree graphs. There is, however, a lot of interest in the interm…

math.CO2020

On directed analogues of expander and hyperfinite graph sequences

Endre Csóka, Łukasz Grabowski

We introduce and study analogues of expander and hyperfinite graph sequences in the context of directed acyclic graphs, which we call "extender" and "hypershallow" graph sequences,…

math.CO2020★ 3 cited

Sumsets of Semiconvex sets

Imre Ruzsa, Jozsef Solymosi

We investigate additive properties of sets $A,$ where $A = {a_{1}, a_{2}, \dots, a_{k}}$ is a monotone increasing set of real numbers, and the differences of consecutive elements are all…

math.CO2020

Exponential multivalued forbidden configurations

Travis Dillon, Attila Sali

The forbidden number $forb (m, F)$ , which denotes the maximum number of unique columns in an $m$ -rowed $(0, 1)$ -matrix with no submatrix that is a row and column permutation…

math.CO2020

Shattered matchings in intersecting hypergraphs

Peter Frankl, Janos Pach

Let $X$ be an $n$ -element set, where $n$ is even. We refute a conjecture of J. Gordon and Y. Teplitskaya, according to which, for every maximal intersecting family $F$ of…

math.CO2020★ 2 cited

On the number of forests and connected spanning subgraphs

Márton Borbényi, Péter Csikvári, Haoran Luo

Let $F (G)$ be the number of forests of a graph $G$ . Similarly let $C (G)$ be the number of connected spanning subgraphs of a connected graph $G$ . We bound $F (G)$ and $C (G)$ for regu…

math.CO2020

The devil's staircase for chip-firing on random graphs and on graphons

Viktor Kiss, Lionel Levine, Lilla Tóthmérész

We study the behavior of the activity of the parallel chip-firing upon increasing the number of chips on an Erdős--Rényi random graph. We show that in various situations the result…

math.CO2020

Largest family without a pair of posets on consecutive levels of the Boolean lattice

Gyula O. H. Katona, Jimeng Xiao

Suppose $k \geq 2$ is an integer. Let $Y_{k}$ be the poset with elements $x_{1}, x_{2}, y_{1}, y_{2}, \dots, y_{k - 1}$ such that $y_{1} < y_{2} < \dots < y_{k - 1} < x_{1}, x_{2}$ and let $Y_{k}^{'}$ be th…

math.CO2020★ 1 cited

The number of triangles is more when they have no common vertex

Chuanqi Xiao, Gyula O. H. Katona

By the theorem of Mantel $[5]$ it is known that a graph with $n$ vertices and $⌊ \frac{n ^{2}}{4} ⌋ + 1$ edges must contain a triangle. A theorem of Erdős gives a strength…

math.CO2020★ 29 cited

Induced and non-induced poset saturation problems

Balázs Keszegh, Nathan Lemons, Ryan R. Martin +2

A subfamily $G \subseteq F \subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $F$ if there exists a bijection $i:P\rightarrow \ma…

math.CO2020

An almost optimal bound on the number of intersections of two simple polygons

Eyal Ackerman, Balázs Keszegh, Günter Rote

What is the maximum number of intersections of the boundaries of a simple $m$ -gon and a simple $n$ -gon, assuming general position? This is a basic question in combinatorial geometr…

On non-adaptive majority problems of large query size

On Turán numbers of the complete 4-graphs

Computing the covering radius of a polytope with an application to lonely runners

Flows on measurable spaces

On directed analogues of expander and hyperfinite graph sequences

Sumsets of Semiconvex sets

Exponential multivalued forbidden configurations

Shattered matchings in intersecting hypergraphs

On the number of forests and connected spanning subgraphs

The devil's staircase for chip-firing on random graphs and on graphons

Largest family without a pair of posets on consecutive levels of the Boolean lattice

The number of triangles is more when they have no common vertex

Induced and non-induced poset saturation problems

An almost optimal bound on the number of intersections of two simple polygons

On Turán numbers of the complete $4$ -graphs