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

22 papers · 2 filters

math.CO2016

Bounds on the 2-domination number

Csilla Bujtás, Szilárd Jaskó

In a graph $G$ , a set $D \subseteq V (G)$ is called 2-dominating set if each vertex not in $D$ has at least two neighbors in $D$ . The 2-domination number $γ_{2} (G)$ is the minimum card…

math.CO2016★ 12 cited

Note on k-planar crossing numbers

János Pach, László A. Székely, Csaba D. Tóth +1

The crossing number $cr (G)$ of a graph $G = (V, E)$ is the smallest number of edge crossings over all drawings of $G$ in the plane. For any $k \geq 1$ , the $k$ -planar crossing number of…

math.CO2016★ 3 cited

Expanders with superquadratic growth

Antal Balog, Oliver Roche-Newton, Dmitry Zhelezov

We will prove several expanders with exponent strictly greater than $2$ . For any finite set $A \subset R$ , we prove the following six-variable expander results: \begin{alig…

math.CO2016★ 42 cited

Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs

Christian Reiher, Vojtěch Rödl, Andrzej Ruciński +2

We show that every 3-uniform hypergraph with $n$ vertices and minimum vertex degree at least $(5/9 + o (1)) (2 n)$ contains a tight Hamiltonian cycle. Known lower bound constructi…

math.CO2016★ 1 cited

Measures on the square as sparse graph limits

Dávid Kunszenti-Kovács, László Lovász, Balázs Szegedy

We study a metric on the set of finite graphs in which two graphs are considered to be similar if they have similar bounded dimensional "factors". We show that limits of convergent…

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★ 39 cited

An Erdős-Gallai type theorem for uniform hypergraphs

Akbar Davoodi, Ervin Győri, Abhishek Methuku +1

A well-known theorem of Erdős and Gallai asserts that a graph with no path of length $k$ contains at most $\frac{1}{2} (k - 1) n$ edges. Recently Győri, Katona and Lemons gave an exten…

math.CO2016★ 1 cited

Better upper bounds on the Füredi-Hajnal limits of permutations

Josef Cibulka, Jan Kynčl

A binary matrix is a matrix with entries from the set ${0, 1}$ . We say that a binary matrix $A$ contains a binary matrix $S$ if $S$ can be obtained from $A$ by removal of some row…

math.CO2016★ 15 cited

Families with no $s$ pairwise disjoint sets

Peter Frankl, Andrey Kupavskii

For integers $n \geq s \geq 2$ let $e (n, s)$ denote the maximum of $∣ F ∣,$ where $F$ is a family of subsets of an $n$ -element set and $F$ contains no $s$ pairw…

math.CO2016

Dominating sequences in grid-like and toroidal graphs

Boštjan Brešar, Csilla Bujtás, Tanja Gologranc +5

A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy do…

math.CO2016★ 11 cited

Note on Terminal-Pairability in Complete Grid Graphs

Ervin Györi, Tamás Róbert Mezei, Gábor Mészáros

We affirmatively answer and generalize the question of Kubicka, Kubicki and Lehel concerning the path-pairability of high-dimensional complete grid graphs. As an intriguing by-prod…

math.CO2016★ 2 cited

A High Quartets Distance Construction

Benny Chor, Péter L. Erdős, Yonatan Komornik

Given two binary trees on $N$ labeled leaves, the quartet distance between the trees is the number of disagreeing quartets. By permuting the leaves at random, the expected quartets…

math.CO2016★ 2 cited

Not all simple looking degree sequence problems are easy

Péter L. Erdős, István Miklós

Degree sequence (DS) problems are around for at least hundred twenty years, and with the advent of network science, more and more complicated, structured DS problems were invented.…

math.CO2016★ 4 cited

Monochromatic paths for the integers

João Guerreiro, Imre Z. Ruzsa, Manuel Silva

Recall that van der Waerden's theorem states that any finite coloring of the naturals has arbitrarily long monochromatic arithmetic sequences. We explore questions about the set of…

math.CO2016★ 10 cited

On the Hamiltonicity of triple systems with high minimum degree

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht +1

We show that every 3-uniform hypergraph with minimum vertex degree at least $0.8 (2 n - 1)$ contains a tight Hamiltonian cycle.

math.CO2016

The parity search problem

Christian Reiher

We prove that for any positive integers $n$ and $d$ there exists a collection consisting of $f = d lo g n + O (1)$ subsets $A_{1}, A_{2}, \dots, A_{f}$ of $[n]$ such that for any two distinct…

math.CO2016

The minimum number of vertices in uniform hypergraphs with given domination number

Csilla Bujtás, Balázs Patkós, Zsolt Tuza +1

The \textit{domination number} $γ (H)$ of a hypergraph $H = (V (H), E (H)$ is the minimum size of a subset $D \subset V (H$ of the vertice…

math.CO2016★ 8 cited

Ramsey numbers for bipartite graphs with small bandwidth

Guilherme O. Mota, Gábor N. Sárközy, Mathias Schacht +1

We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers fo…

math.CO2016★ 14 cited

Convergence of graphs with intermediate density

Péter E. Frenkel

We propose a notion of graph convergence that interpolates between the Benjamini--Schramm convergence of bounded degree graphs and the dense graph convergence developed by László L…

math.CO2016

Bounds on the Game Transversal Number in Hypergraphs

Csilla Bujtás, Michael A. Henning, Zsolt Tuza

Let $H = (V, E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order $\nH = |V|$ and size $\mH = |E|$. A transversal in $H$ is a subset of vertices in $H$ that has a nonem…

math.CO2016★ 6 cited

New classes of degree sequences with fast mixing swap Markov chain sampling

Péter L. Erdős, István Miklós, Zoltán Toroczkai

In network modeling of complex systems one is often required to sample random realizations of networks that obey a given set of constraints, usually in form of graph measures. A mu…

math.CO2016★ 4 cited

Constructions for the optimal pebbling of grids

Ervin Győri, Gyula Y. Katona, László F. Papp

In [C. Xue, C. Yerger: Optimal Pebbling on Grids, Graphs and Combinatorics] the authors conjecture that if every vertex of an infinite square grid is reachable from a pebble distri…

Bounds on the 2-domination number

Note on k-planar crossing numbers

Expanders with superquadratic growth

Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs

Measures on the square as sparse graph limits

Pach's selection theorem does not admit a topological extension

An Erdős-Gallai type theorem for uniform hypergraphs

Better upper bounds on the Füredi-Hajnal limits of permutations

Families with no s pairwise disjoint sets

Dominating sequences in grid-like and toroidal graphs

Note on Terminal-Pairability in Complete Grid Graphs

A High Quartets Distance Construction

Not all simple looking degree sequence problems are easy

Monochromatic paths for the integers

On the Hamiltonicity of triple systems with high minimum degree

The parity search problem

The minimum number of vertices in uniform hypergraphs with given domination number

Ramsey numbers for bipartite graphs with small bandwidth

Convergence of graphs with intermediate density

Bounds on the Game Transversal Number in Hypergraphs

New classes of degree sequences with fast mixing swap Markov chain sampling

Constructions for the optimal pebbling of grids

Families with no $s$ pairwise disjoint sets