Source author record

Barnabás Janzer

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

ResearcherUnclaimed source record

math.CO math.MG

Catalog footprint

Research overview

7works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A note on the orientation covering number

Given a graph $G$ , its orientation covering number $σ(G)$ is the smallest non-negative integer $k$ with the property that we can choose $k$ orientations of $G$ such that whenever $x, y, z$ are vertices of $G$ with $xy,xz\in E(G)$ then there is a chosen orientation in which both $xy$ and $xz$ are oriented away from $x$ . Esperet, Gimbel and King showed that $σ(G)\leq σ\left(K_{χ(G)}\right)$ , where $χ(G)$ is the chromatic number of $G$ , and asked whether we always have equality. In this note we prove that it is indeed always the case that $σ(G)=σ(K_{χ(G)})$ . We also determine the exact value of $σ(K_n)$ explicitly for `most' values of $n$ .

preprint2020arXiv

Generalizations of the Ruzsa-Szemerédi and rainbow Turán problems for cliques

Considering a natural generalization of the Ruzsa-Szemerédi problem, we prove that for any fixed positive integers $r,s$ with $r<s$ , there are graphs on $n$ vertices containing $n^{r}e^{-O(\sqrt{\log{n}})}=n^{r-o(1)}$ copies of $K_s$ such that any $K_r$ is contained in at most one $K_s$ . We also give bounds for the generalized rainbow Turán problem $\operatorname{ex}(n, H,$ rainbow- $F)$ when $F$ is complete. In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer, showing that there are properly edge-coloured graphs on $n$ vertices with $n^{r-1-o(1)}$ copies of $K_r$ such that no $K_r$ is rainbow.

preprint2020arXiv

Large hypergraphs without tight cycles

An $r$ -uniform tight cycle of length $\ell>r$ is a hypergraph with vertices $v_1,\dots,v_\ell$ and edges $\{v_i,v_{i+1},\dots,v_{i+r-1}\}$ (for all $i$ ), with the indices taken modulo $\ell$ . It was shown by Sudakov and Tomon that for each fixed $r\geq 3$ , an $r$ -uniform hypergraph on $n$ vertices which does not contain a tight cycle of any length has at most $n^{r-1+o(1)}$ hyperedges, but the best known construction (with the largest number of edges) only gives $Ω(n^{r-1})$ edges. In this note we prove that, for each fixed $r\geq 3$ , there are $r$ -uniform hypergraphs with $Ω(n^{r-1}\log n/\log\log n)$ edges which contain no tight cycles, showing that the $o(1)$ term in the exponent of the upper bound is necessary.

preprint2020arXiv

The generalised rainbow Turán problem for cycles

Given an edge-coloured graph, we say that a subgraph is rainbow if all of its edges have different colours. Let $\operatorname{ex}(n,H,$ rainbow- $F)$ denote the maximal number of copies of $H$ that a properly edge-coloured graph on $n$ vertices can contain if it has no rainbow subgraph isomorphic to $F$ . We determine the order of magnitude of $\operatorname{ex}(n,C_s,$ rainbow- $C_t)$ for all $s,t$ with $s\not =3$ . In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer by showing that $\operatorname{ex}(n,C_{2k},$ rainbow- $C_{2k})$ is $Θ(n^{k-1})$ if $k\geq 3$ and $Θ(n^2)$ if $k=2$ . We also determine the order of magnitude of $\operatorname{ex}(n,P_\ell,$ rainbow- $C_{2k})$ for all $k,\ell\geq 2$ , where $P_\ell$ denotes the path with $\ell$ edges.

preprint2019arXiv

A note on antichains in the continuous cube

It is well-known that an antichain in the poset $[0,1]^n$ must have measure zero. Engel, Mitsis, Pelekis and Reiher showed that in fact it must have $(n-1)$ -dimensional Hausdorff measure at most $n$ , and they conjectured that this bound can be attained. In this note we show that, for every $n$ , such an antichain does indeed exist.

preprint2019arXiv

Projections of antichains

A subset $A$ of $\mathbb{Z}^n$ is called a weak antichain if it does not contain two elements $x$ and $y$ satisfying $x_i<y_i$ for all $i$ . Engel, Mitsis, Pelekis and Reiher showed that for any weak antichain $A$ , the sum of the sizes of its $(n-1)$ -dimensional projections must be at least as large as its size $|A|$ . They asked what the smallest possible value of the gap between these two quantities is in terms of $|A|$ . We answer this question by giving an explicit weak antichain attaining this minimum for each possible value of $|A|$ . In particular, we show that sets of the form $A_N=\{x\in\mathbb{Z}^n: 0\leq x_j\leq N-1$ for all $j$ and $x_i=0$ for some $i\}$ minimise the gap among weak antichains of size $|A_N|$ .

preprint2017arXiv

A New Upper Bound for Cancellative Pairs

A pair $(\mathcal{A},\mathcal{B})$ of families of subsets of an $n$ -element set is called cancellative if whenever $A,A'\in\mathcal{A}$ and $B\in\mathcal{B}$ satisfy $A\cup B=A'\cup B$ , then $A=A'$ , and whenever $A\in\mathcal{A}$ and $B,B'\in\mathcal{B}$ satisfy $A\cup B=A\cup B'$ , then $B=B'$ . It is known that there exist cancellative pairs with $|\mathcal{A}||\mathcal{B}|$ about $2.25^n$ , whereas the best known upper bound on this quantity is $2.3264^n$ . In this paper we improve this upper bound to $2.2682^n$ . Our result also improves the best known upper bound for Simonyi's sandglass conjecture for set systems.

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.

Barnabás Janzer

Research overview

Is this your work?

7 publications

A note on the orientation covering number

Generalizations of the Ruzsa-Szemerédi and rainbow Turán problems for cliques

Large hypergraphs without tight cycles

The generalised rainbow Turán problem for cycles

A note on antichains in the continuous cube

Projections of antichains

A New Upper Bound for Cancellative Pairs

See the researcher in context

Building this map preview