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

Best possible bounds on the double-diversity of intersecting hypergraphs

Peter Frankl, Jian Wang

For a family $F \subset (k [ n ])$ and two elements $x, y \in [n]$ define $F (x ˉ, y ˉ) = {F \in F : x \in / F, y \in / F}$ . The double-di…

Rainbow saturation for complete graphs

Debsoumya Chakraborti, Kevin Hendrey, Ben Lund +1

We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph $Γ$ is called $H$ -rainbow saturated if $Γ$ does not contain a rainbow copy…

On ordered Ramsey numbers of tripartite 3-uniform hypergraphs

Martin Balko, Máté Vizer

For an integer $k \geq 2$ , an ordered $k$ -uniform hypergraph $H = (H, <)$ is a $k$ -uniform hypergraph $H$ together with a fixed linear ordering $<$ of its vertex set. The or…

Cutting corners

Andrey Kupavskii, Arsenii Sagdeev, Dmitrii Zakharov

We say that a subset $M$ of $R^{n}$ is exponentially Ramsey if there are $ε > 0$ and $n_{0}$ such that $χ (R^{n}, M) \geq (1 + ε)^{n}$ for any $n > n_{0}$ , where $χ (R^{n}, M)$ stan…

Monochromatic spanning trees and matchings in ordered complete graphs

János Barát, András Gyárfás, Géza Tóth

Two independent edges in ordered graphs can be nested, crossing or separated. These relations define six types of subgraphs, depending on which relations are forbidden. We refine a…

Count and cofactor matroids of highly connected graphs

Dániel Garamvölgyi, Tibor Jordán, Csaba Király

We consider two types of matroids defined on the edge set of a graph $G$ : count matroids $M_{k, ℓ} (G)$ , in which independence is defined by a sparsity count involving the…

The extensible No-Three-In-Line problem

Dániel T. Nagy, Zoltán Lóránt Nagy, Russ Woodroofe

The classical No-Three-In-Line problem seeks the maximum number of points that may be selected from an $n \times n$ grid while avoiding a collinear triple. The maximum is well known…

Generalizing Körner's graph entropy to graphons

Viktor Harangi, Xueyan Niu, Bo Bai

Körner introduced the notion of graph entropy in 1973 as the minimal code rate of a natural coding problem where not all pairs of letters can be distinguished in the alphabet. Late…

math.CO2022★ 2 cited

On pattern-avoiding permutons

Frederik Garbe, Jan Hladký, Gábor Kun +1

The theory of limits of permutations leads to limit objects called permutons, which are certain Borel measures on the unit square. We prove that permutons avoiding a given permutat…

Orientation of good covers

Péter Ágoston, Gábor Damásdi, Balázs Keszegh +1

We study systems of orientations on triples that satisfy the following so-called interiority condition: $↺ (A B D) = ↺ (B C D) = ↺ (C A D) = 1$ impl…

Turán numbers $T (n, 5, 3)$ and graphs without induced $5$ -cycles

Iliya Bluskov, Jan de Heer, Alexander Sidorenko

Turán number $T (n, 5, 3)$ is the minimum size of a system of triples out of a base set $X$ of $n$ elements such that every quintuple in $X$ contains a triple from the system. The exa…

Random cluster model on regular graphs

Ferenc Bencs, Márton Borbényi, Péter Csikvári

For a graph $G = (V, E)$ with $v (G)$ vertices the partition function of the random cluster model is defined by $Z_{G} (q, w) = A \subseteq E (G) \sum q^{k (A)} w^{∣ A ∣},$ where $k (A)$ denotes…

math.CO2022★ 4 cited

Turán numbers of $r$ -graphs on $r + 1$ vertices

Alexander Sidorenko

Let $H_{k}^{r}$ denote an $r$ -uniform hypergraph with $k$ edges and $r + 1$ vertices, where $k \leq r + 1$ (it is easy to see that such a hypergraph is unique up to isomorphism). The known…

math.CO2022★ 4 cited

The sequence of prime gaps is graphic

Péter L. Erdős, Gergely Harcos, Shubha R. Kharel +3

Let us call a simple graph on $n \geq 2$ vertices a prime gap graph if its vertex degrees are $1$ and the first $n - 1$ prime gaps. We show that such a graph exists for every large $n…

math.CO2022★ 2 cited

Approximate Sampling of Graphs with Near- $P$ -stable Degree Intervals

Péter L. Erdős, Tamás Róbert Mezei, István Miklós

The approximate uniform sampling of graph realizations with a given degree sequence is an everyday task in several social science, computer science, engineering etc. projects. One…

New results on graph matching from degree preserving growth

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

The recently introduced \emph{Degree Preserving Growth} model (Nature Physics, \DOI{10.1038/s41567-021-01417-7}) uses matchings to insert new vertices of prescribed degrees into th…

math.CO2022★ 6 cited

Improved replica bounds for the independence ratio of random regular graphs

Viktor Harangi

Studying independent sets of maximum size is equivalent to considering the hard-core model with the fugacity parameter $λ$ tending to infinity. Finding the independence ratio of ra…

math.CO2022★ 5 cited

Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings

Nóra Frankl, Andrey Kupavskii, Arsenii Sagdeev

In 2008, Schmidt and Tuller stated a conjecture concerning optimal packing and covering of integers by translates of a given three-point set. In this note, we confirm their conject…