Source author record

Andrzej Grzesik

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms

Catalog footprint

Research overview

12works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Cycles of a given length in tournaments

We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let $c(\ell)$ be the limit of the ratio of the maximum number of cycles of length $\ell$ in an $n$ -vertex tournament and the expected number of cycles of length $\ell$ in the random $n$ -vertex tournament, when $n$ tends to infinity. It is well-known that $c(3)=1$ and $c(4)=4/3$ . We show that $c(\ell)=1$ if and only if $\ell$ is not divisible by four, which settles a conjecture of Bartley and Day. If $\ell$ is divisible by four, we show that $1+2\cdot\left(2/π\right)^{\ell}\le c(\ell)\le 1+\left(2/π+o(1)\right)^{\ell}$ and determine the value $c(\ell)$ exactly for $\ell = 8$ . We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length $\ell$ when $\ell$ is not divisible by four or $\ell\in\{4,8\}$ .

preprint2022arXiv

On the inducibility of oriented graphs on four vertices

We consider the problem of determining the inducibility (maximum possible asymptotic density of induced copies) of oriented graphs on four vertices. We provide exact values for more than half of the graphs, and very close lower and upper bounds for all the remaining ones. It occurs that, for some graphs, the structure of extremal constructions maximizing density of its induced copies is very sophisticated and complex.

preprint2022arXiv

On tripartite common graphs

A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdos, conjectured that every graph is common. The conjectures by Erdos and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenko's conjecture. Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle-trees, which generalises two theorems by Sidorenko and answers a question by Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle-tree such that the graph obtained by adding T as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most five vertices give a common graph.

preprint2022arXiv

Subgraph densities in $K_r$ -free graphs

In this paper we disprove a conjecture of Lidický and Murphy about the number of copies of a given graph in a $K_r$ -free graph and give an alternative general conjecture. We also prove an asymptotically tight bound on the number of copies of any bipartite graph of radius at most $2$ in a triangle-free graph.

preprint2020arXiv

Covering minimal separators and potential maximal cliques in $P_t$ -free graphs

A graph is called $P_t$ -free} if it does not contain a $t$ -vertex path as an induced subgraph. While $P_4$ -free graphs are exactly cographs, the structure of $P_t$ -free graphs for $t \geq 5$ remains little understood. On one hand, classic computational problems such as Maximum Weight Independent Set (MWIS) and $3$ -Coloring are not known to be NP-hard on $P_t$ -free graphs for any fixed $t$ . On the other hand, despite significant effort, polynomial-time algorithms for MWIS in $P_6$ -free graphs~[SODA 2019] and $3$ -Coloring in $P_7$ -free graphs~[Combinatorica 2018] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes. One of the main tools in the algorithms for MWIS in $P_5$ -free graphs~[SODA 2014] and in $P_6$ -free graphs~[SODA 2019] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to $P_7$ -free graphs and is false in $P_8$ -free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.

preprint2020arXiv

Elusive extremal graphs

We study the uniqueness of optimal solutions to extremal graph theory problems. Lovasz conjectured that every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints so that the resulting set is satisfied by an asymptotically unique graph. This statement is often referred to as saying that `every extremal graph theory problem has a finitely forcible optimum'. We present a counterexample to the conjecture. Our techniques also extend to a more general setting involving other types of constraints.

preprint2020arXiv

Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$ -free graphs

In the classic Maximum Weight Independent Set problem we are given a graph $G$ with a nonnegative weight function on vertices, and the goal is to find an independent set in $G$ of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any $P_6$ -free graph, that is, a graph that has no path on $6$ vertices as an induced subgraph. This improves the polynomial-time algorithm on $P_5$ -free graphs of Lokshtanov et al. (SODA 2014), and the quasipolynomial-time algorithm on $P_6$ -free graphs of Lokshtanov et al (SODA 2016). The main technical contribution leading to our main result is enumeration of a polynomial-size family $\mathcal{F}$ of vertex subsets with the following property: for every maximal independent set $I$ in the graph, $\mathcal{F}$ contains all maximal cliques of some minimal chordal completion of $G$ that does not add any edge incident to a vertex of $I$ .

preprint2016arXiv

Finitely forcible graphons and permutons

We investigate when limits of graphs (graphons) and permutations (permutons) are uniquely determined by finitely many densities of their substructures, i.e., when they are finitely forcible. Every permuton can be associated with a graphon through the notion of permutation graphs. We find permutons that are finitely forcible but the associated graphons are not. We also show that all permutons that can be expressed as a finite combination of monotone permutons and quasirandom permutons are finitely forcible, which is the permuton counterpart of the result of Lovasz and Sos for graphons.

preprint2015arXiv

Avoider-Enforcer star games

In this paper, we study $(1 : b)$ Avoider-Enforcer games played on the edge set of the complete graph on $n$ vertices. For every constant $k\geq 3$ we analyse the $k$ -star game, where Avoider tries to avoid claiming $k$ edges incident to the same vertex. We analyse both versions of Avoider-Enforcer games -- the strict and the monotone -- and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases $f^{mon}_\mathcal{F}$ , $f^-_\mathcal{F}$ and $f^+_\mathcal{F}$ , where $\mathcal{F}$ is the hypergraph of the game.

preprint2013arXiv

From directed path to linear order - the best choice problem for powers of directed path

We examine the evolution of the best choice algorithm and the probability of its success from a directed path to the linear order of the same cardinality through $k$ th powers of a directed path, $1 \leq k < n$ . The vertices of a $k$ th power of a directed path of a known length $n$ are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already come. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). It is shown that the probability of success $p_n$ for the optimal algorithm for the $k$ th power of a directed path satisfies $p_n = Θ(n^{-1/(k+1)})$ . We also consider the case when the selector knows the distance in the underlying path between each two vertices that are joined by an edge in the induced graph. An optimal algorithm for this choice problem is presented. The exact probability of success when using this algorithm is given.

preprint2013arXiv

Interval edge-colorings of K_{1,m,n}

In this note we prove that K_{1,m,n} is interval edge-colorable if and only if gcd(m+1,n+1)=1. It settles in the affirmative a conjecture of Petrosyan.

preprint2012arXiv

On the maximum number of five-cycles in a triangle-free graph

Using Razborov's flag algebras we show that a triangle-free graph on n vertices contains at most (n/5)^5 cycles of length five. It settles in the affirmative a conjecture of Erdos.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Andrzej Grzesik

Research overview

Is this your work?

12 publications

Cycles of a given length in tournaments

On the inducibility of oriented graphs on four vertices

On tripartite common graphs

Subgraph densities in $K_r$ -free graphs

Covering minimal separators and potential maximal cliques in $P_t$ -free graphs

Elusive extremal graphs

Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$ -free graphs

Finitely forcible graphons and permutons

Avoider-Enforcer star games

From directed path to linear order - the best choice problem for powers of directed path

Interval edge-colorings of K_{1,m,n}

On the maximum number of five-cycles in a triangle-free graph

See the researcher in context

Building this map preview

Andrzej Grzesik

Research overview

Is this your work?

12 publications

Cycles of a given length in tournaments

On the inducibility of oriented graphs on four vertices

On tripartite common graphs

Subgraph densities in KrK_rKr​-free graphs

Covering minimal separators and potential maximal cliques in PtP_tPt​-free graphs

Elusive extremal graphs

Polynomial-time algorithm for Maximum Weight Independent Set on P6P_6P6​-free graphs

Finitely forcible graphons and permutons

Avoider-Enforcer star games

From directed path to linear order - the best choice problem for powers of directed path

Interval edge-colorings of K_{1,m,n}

On the maximum number of five-cycles in a triangle-free graph

See the researcher in context

Building this map preview

Subgraph densities in $K_r$ -free graphs

Covering minimal separators and potential maximal cliques in $P_t$ -free graphs

Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$ -free graphs