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

An Erdős-Gallai type theorem for vertex colored graphs

Nika Salia, Casey Tompkins, Oscar Zamora

While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdős and Gallai on $P_{k}$ -free graphs. They proved that an…

Generalized Turán problems for even cycles

Dániel Gerbner, Ervin Győri, Abhishek Methuku +1

Given a graph $H$ and a set of graphs $F$ , let $e x (n, H, F)$ denote the maximum possible number of copies of $H$ in an $F$ -free graph on $n$ vertices. We i…

Tilings of the plane with unit area triangles of bounded diameter

Andrey Kupavskii, János Pach, Gábor Tardos

There exist tilings of the plane with pairwise noncongruent triangles of equal area and bounded perimeter. Analogously, there exist tilings with triangles of equal perimeter, the a…

math.CO2017★ 15 cited

Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences

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

Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. Several results were proved on rapidly mixing Markov ch…

Two extensions of the Erdős-Szekeres problem

Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach +1

According to Suk's breakthrough result on the Erdos-Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex…

math.CO2017★ 10 cited

On the Turán number of some ordered even cycles

Ervin Győri, Dániel Korándi, Abhishek Methuku +3

A classical result of Bondy and Simonovits in extremal graph theory states that if a graph on $n$ vertices contains no cycle of length $2 k$ then it has at most $O (n^{1 + 1/ k})$ edges…

Vertex-flames in countable rooted digraphs preserving an Erdős-Menger separation for each vertex

Attila Joó

It follows from a theorem of Lovász that if $D$ is a finite digraph with $r \in V (D)$ then there is a spanning subdigraph $E$ of $D$ such that for every vertex $v \neq = r$ t…

Navigating Between Packings of Graphic Sequences

Peter L. Erdos, Michael Ferrara, Stephen G. Hartke

Let $π_{1} = (d_{1}^{(1)}, \dots, d_{n}^{(1)})$ and $π_{2} = (d_{1}^{(2)}, \dots, d_{n}^{(2)})$ be graphic sequences. We say they \emph{pack} if there exist edge-disjoint realizations $G_{1}$ and $G_…

math.CO2017★ 20 cited

Exploring the tiers of rooted phylogenetic network space using tail moves

Remie Janssen, Mark Jones, Péter L. Erdős +2

Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rNNI (rooted Nearest Neighbour Interchange) and rSPR (rooted Subtree Prune and…

Convex sequences may have thin additive bases

Imre Z. Ruzsa, Dmitrii Zhelezov

For a fixed $c > 0$ we construct an arbitrarily large set $B$ of size $n$ such that its sum set $B + B$ contains a convex sequence of size $c n^{2}$ , answering a question of Hegarty.

math.CO2017★ 2 cited

Multi-Symbol Forbidden Configurations

Keaton Ellis, Baian Liu, Attila Sali

An $r$ -matrix is a matrix with symbols in ${0, 1, \dots, r - 1}$ . A matrix is simple if it has no repeated columns. Let the support of a matrix $F$ , $supp (F)$ be the largest si…

Betweenness Structures of Small Linear Co-Size

Péter G. N. Szabó

One way to study the combinatorics of finite metric spaces is to study the betweenness relation associated with the metric space. In the hypergraph metrization problem, one has to…

math.CO2017★ 5 cited

Turán number of an induced complete bipartite graph plus an odd cycle

Beka Ergemlidze, Ervin Győri, Abhishek Methuku

Let $k \geq 2$ be an integer. We show that if $s = 2$ and $t \geq 2$ , or $s = t = 3$ , then the maximum possible number of edges in a $C_{2 k + 1}$ -free graph containing no induced copy…

Forbidden subposet problems for traces of set families

Dániel Gerbner, Balázs Patkós, Máté Vizer

In this paper we introduce a problem that bridges forbidden subposet and forbidden subconfiguration problems. The sets $F_{1}, F_{2}, \dots, F_{∣ P ∣}$ form a copy of a poset $P$ , if there…

Mobile vs. point guards

Ervin Győri, Tamás Róbert Mezei

We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bou…

Asymptotics for the Turán number of Berge- $K_{2, t}$

Dániel Gerbner, Abhishek Methuku, Máté Vizer

Let $F$ be a graph. A hypergraph is called Berge- $F$ if it can be obtained by replacing each edge of $F$ by a hyperedge containing it. Let $F$ be a family of graphs. The…

Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands

Lucas Colucci, Péter L. Erdős, Ervin Győri +1

We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on t…

One more remark on the adjoint polynomial

Ferenc Bencs

The adjoint polynomial of $G$ is \[h(G,x)=\sum_{k=1}^n(-1)^{n-k}a_k(G)x^k,\] where $a_{k} (G)$ denotes the number of ways one can cover all vertices of the graph $G$ by exactly $k$ di…

Extensions of a theorem of Erdős on nonhamiltonian graphs

Zoltán Füredi, Alexandr Kostochka, Ruth Luo

Let $n, d$ be integers with $1 \leq d \leq ⌊ \frac{n - 1}{2} ⌋$ , and set $h (n, d) := (2 n - d) + d^{2}$ . Erdős proved that when $n \geq 6 d$ , each nonhamilto…

A Note on the Polytope of Bipartite TSP

Gergely Kovács, Zsolt Tuza, Béla Vizvári +1

The main result of this paper is that the polytope of the bipartite TSP is significantly different from that of the general TSP. Comb inequalities are known as facet defining ones…

Forbidden Families of Minimal Quadratic and Cubic Configurations

Attila Sali, Sam Spiro

A matrix is \emph{simple} if it is a (0,1)-matrix and there are no repeated columns. Given a (0,1)-matrix $F$ , we say a matrix $A$ has $F$ as a \emph{configuration}, denoted $F\pre…

On trees with real rooted independence polynomial

Ferenc Bencs

The independence polynomial of a graph $G$ is \[I(G,x)=\sum\limits_{k\ge 0}i_k(G)x^k,\] where $i_{k} (G)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0(G)=…

math.CO2017★ 10 cited

A superlinear lower bound on the number of 5-holes

Oswin Aichholzer, Martin Balko, Thomas Hackl +5

Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$ -hol…