Source author record

András Pluhár

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A discrepancy version of the Hajnal-Szemerédi theorem

A perfect $K_r$ -tiling in a graph $G$ is a collection of vertex-disjoint copies of the clique $K_r$ in $G$ covering every vertex of $G$ . The famous Hajnal--Szemerédi theorem determines the minimum degree threshold for forcing a perfect $K_r$ -tiling in a graph $G$ . The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph $G$ labels from $\{-1,1\}$ , and one seeks substructures $F$ of $G$ that have `high' discrepancy (i.e. the sum of the labels of the edges in $F$ is far from $0$ ). In this paper we determine the minimum degree threshold for a graph to contain a perfect $K_r$ -tiling of high discrepancy.

preprint2020arXiv

On the discrepancies of graphs

In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph $G$ , $\{-1, 1\}$ labels are assigned to the edges, and we consider a family $\mathcal{S}_G$ of (spanning) subgraphs of certain types, among others spanning trees, Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of $\mathcal{S}_G$ , for every labeling.

preprint2016arXiv

On the complexity of Chooser-Picker positional games

Two new versions of the so-called Maker-Breaker Positional Games are defined by József Beck in [{\em Combinatorica} {\bf 22}(2) (2002) 169--216]. He defines two players, Picker and Chooser. In each round, Picker takes a pair of elements not already selected and Chooser keeps one and returns the other to Picker. In the Picker-Chooser version Picker plays as Maker and Chooser plays as Breaker, while the roles are swapped in the Chooser-Picker version. The outcome of these games is sometimes very similar to that of the traditional Maker-Breaker games. Here we show that both Picker-Chooser and Chooser-Picker games are NP-hard, which gives support to the paradigm that the games behave similarly while being quite different in definition. We also investigate the pairing strategies for Maker-Breaker games, and apply these results to the game called "Snaky."

preprint2016arXiv

On the path separation number of graphs

A path separator of a graph $G$ is a set of paths $\mathcal{P}=\{P_1,\ldots,P_t\}$ such that for every pair of edges $e,f\in E(G)$ , there exist paths $P_e,P_f\in\mathcal{P}$ such that $e\in E(P_e)$ , $f\not\in E(P_e)$ , $e\not\in E(P_f)$ and $f\in E(P_f)$ . The path separation number of $G$ , denoted ${\rm psn}(G)$ , is the smallest number of paths in a path separator. We shall estimate the path separation number of several graph families, including complete graphs, random graph, the hypercube, and discuss general graphs as well.

preprint2016arXiv

The diameter game

A large class of Positional Games are defined on the complete graph on $n$ vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given -- usually monotone -- property. Here we introduce the $d$ -diameter game, which means that Maker wins iff the diameter of his subgraph is at most $d$ . We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the $2$ -diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose $2$ edges in each turn whereas Breaker can choose as many as $(1/9)n^{1/8}/(\ln n)^{3/8}$ . In addition, we investigate $d$ -diameter games for $d\ge 3$ . The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case.

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.

András Pluhár

Research overview

Is this your work?

5 publications

A discrepancy version of the Hajnal-Szemerédi theorem

On the discrepancies of graphs

On the complexity of Chooser-Picker positional games

On the path separation number of graphs

The diameter game

See the researcher in context

Building this map preview