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

Degree-preserving graph dynamics -- a versatile process to construct random networks

Péter L. Erdős, Shubha R. Kharel, Tamás R. Mezei +1

Real-world networks evolve over time via additions or removals of vertices and edges. In current network evolution models, vertex degree varies or grows arbitrarily. A recently int…

Max-norm Ramsey Theory

Nóra Frankl, Andrey Kupavskii, Arsenii Sagdeev

Given a metric space $M$ that contains at least two points, the chromatic number $χ (R_{\infty}^{n}, M)$ is defined as the minimum number of c…

Saturated $2$ -planar drawings with few edges

János Barát, Géza Tóth

A drawing of a graph is $k$ -plane if every edge contains at most $k$ crossings. A $k$ -plane drawing is saturated if we cannot add any edge so that the drawing remains $k$ -plane. It…

On positive hypergraphs

Alexander Sidorenko

Camarena, Csóka, Hubai, Lippner, and Lovász introduced the notion of positive graphs. This notion naturally extends to $r$ -uniform hypergraphs. In the case when $r$ is odd, we prov…

Large Monochromatic Components of Small Diameter

Erik Carlson, Ryan R. Martin, Bo Peng +1

Gyárfás conjectured in 2011 that every $r$ -edge-colored $K_{n}$ contains a monochromatic component of bounded ("perhaps three") diameter on at least $n / (r - 1)$ vertices. Letzter prove…

Ramsey simplicity of random graphs

Simona Boyadzhiyska, Dennis Clemens, Shagnik Das +1

A graph $G$ is $q$ -Ramsey for another graph $H$ if in any $q$ -edge-colouring of $G$ there is a monochromatic copy of $H$ , and the classic Ramsey problem asks for the minimum number…

The Lovász-Cherkassky theorem for locally finite graphs with ends

Raphael W. Jacobs, Attila Joó, Paul Knappe +2

Lovász and Cherkassky discovered independently that, if $G$ is a finite graph and $T \subseteq V (G)$ such that the degree $d_{G} (v)$ is even for every vertex $v \in V (G) ∖ T$ , t…

Extremal problems of double stars

Ervin Győri, Runze Wang, Spencer Woolfson

In a generalized Turán problem, two graphs $H$ and $F$ are given and the question is the maximum number of copies of $H$ in an $F$ -free graph of order $n$ . In this paper, we study…

Large vertex-flames in uncountable digraphs

Florian Gut, Attila Joó

The study of minimal subgraphs witnessing a connectivity property is an important field in graph theory. The foundation for large flames has been laid by Lovász: Let $D = (V, E)$ be…

A slightly better bound on the crossing number in terms of the pair-crossing number

János Karl, Géza Tóth

The crossing number of a graph $G$ , ${\mbox{cr}}(G)$, is the minimum number of crossings, the pair-crossing number, ${\mbox{pcr}}(G)$, is the minimum number of pairs of crossing ed…

On the hollow enclosed by convex sets

Jenő Lehel, Géza Tóth

For $n \leq d$ , a family $F = {C_{0}, C_{1}, \dots, C_{n}}$ of compact convex sets in $R^{d}$ is called an $n$ -critical family provided any $n$ members of $F$ have a non-empty…

On the Rényi-Ulam Game with Restricted Size Queries

Ádám Fraknói, Dávid Márton, Dániel Simon +1

We investigate the following version of the well-known Rényi-Ulam game. Two players - the Questioner and the Responder - play against each other. The Responder thinks of a number f…

A Markov chain on the solution space of edge-colorings of bipartite graphs

Letong Hong, Istvan Miklos

In this paper, we exhibit an irreducible Markov chain $M$ on the edge $k$ -colorings of bipartite graphs based on certain properties of the solution space. We show that diameter of…

Erdős-Szekeres theorem for $k$ -flats

Imre Bárány, Gil Kalai, Attila Pór

We extend the famous Erdős-Szekeres theorem to $k$ -flats in $R^{d}$

Renitent lines

Bence Csajbók, Peter Sziklai, Zsuzsa Weiner

There are many examples for point sets in finite geometry, which behave "almost regularly" in some (well-defined) sense, for instance they have "almost regular" line-intersection n…

On strengthenings of the intersecting shadow theorem

P. Frankl, G. O. H. Katona

Let $n > k > t \geq j \geq 1$ be integers. Let $X$ be an $n$ -element set, $(k X)$ the collection of its $k$ -subsets. A family $F \subset (k X)$ is called $t$ …