BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Balazs Patkos

Balazs Patkos contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

6 published item(s)

preprint2020arXiv

On $L$-close Sperner systems

For a set $L$ of positive integers, a set system $\mathcal{F} \subseteq 2^{[n]}$ is said to be $L$-close Sperner, if for any pair $F,G$ of distinct sets in $\mathcal{F}$ the skew distance $sd(F,G)=\min\{|F\setminus G|,|G\setminus F|\}$ belongs to $L$. We reprove an extremal result of Boros, Gurvich, and Milani\v c on the maximum size of $L$-close Sperner set systems for $L=\{1\}$ and generalize to $|L|=1$ and obtain slightly weaker bounds for arbitrary $L$. We also consider the problem when $L$ might include 0 and reprove a theorem of Frankl, Füredi, and Pach on the size of largest set systems with all skew distances belonging to $L=\{0,1\}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Induced and non-induced forbidden subposet problems

The problem of determining the maximum size $La(n,P)$ that a $P$-free subposet of the Boolean lattice $B_n$ can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of $La^*(n,P)$, the maximum size that an induced $P$-free subposet of the Boolean lattice $B_n$ can have for the case when $P$ is the complete two-level poset $K_{r,t}$ or the complete multi-level poset $K_{r,s_1,\dots,s_j,t}$ when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. We also show lower and upper bounds for the non-induced problem in the case when $P$ is the complete three-level poset $K_{r,s,t}$. These bounds determine the asymptotics of $La(n,K_{r,s,t})$ for some values of $s$ independently of the values of $r$ and $t$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Game saturation of intersecting families

We consider the following combinatorial game: two players, Fast and Slow, claim $k$-element subsets of $[n]=\{1,2,...,n\}$ alternately, one at each turn, such that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed $k$-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game's end as long as possible. The game saturation number is the score of the game when both players play according to an optimal strategy. To be precise we have to distinguish two cases depending on which player takes the first move. Let $gsat_F(\mathbb{I}_{n,k})$ and $gsat_S(\mathbb{I}_{n,k})$ denote the score of the saturation game when both players play according to an optimal strategy and the game starts with Fast's or Slow's move, respectively. We prove that $Ω_k(n^{k/3-5}) \le gsat_F(\mathbb{I}_{n,k}),gsat_S(\mathbb{I}_{n,k}) \le O_k(n^{k-\sqrt{k}/2})$ holds.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Identifying codes and searching with balls in graphs

Given a graph $G$ and a positive integer $R$ we address the following combinatorial search theoretic problem: What is the minimum number of queries of the form "does an unknown vertex $v \in V(G)$ belong to the ball of radius $r$ around $u$?" with $u \in V(G)$ and $r\le R$ that is needed to determine $v$. We consider both the adaptive case when the $j$th query might depend on the answers to the previous queries and the non-adaptive case when all queries must be made at once. We obtain bounds on the minimum number of queries for hypercubes, the Erd\H os-Rényi random graphs and graphs of bounded maximum degree .

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Families that remain $k$-Sperner even after omitting an element of their ground set

A family $\cF\subseteq 2^{[n]}$ of sets is said to be $l$-trace $k$-Sperner if for any $l$-subset $L \subset [n]$ the family $\cF|_L=\{F|_L:F \in \cF\}=\{F \cap L: F \in \cF\}$ is $k$-Sperner, i.e. does not contain any chain of length $k+1$. The maximum size that an $l$-trace $k$-Sperner family $\cF \subseteq 2^{[n]}$ can have is denoted by $f(n,k,l)$. For pairs of integers $l<k$, if in a family $\cG$ every pair of sets satisfies $||G_1|-|G_2||<k-l$, then $\cG$ possesses the $(n-l)$-trace $k$-Sperner property. Among such families, the largest one is $\cF_0=\{F\in 2^{[n]}: \lfloor \frac{n-(k-l)}{2}\rfloor+1 \le |F| \le \lfloor \frac{n-(k-l)}{2}\rfloor +k-l\}$ and also $\cF&#39;_0=\{F\in 2^{[n]}: \lfloor \frac{n-(k-l)}{2}\rfloor \le |F| \le \lfloor \frac{n-(k-l)}{2}\rfloor +k-l-1\}$ if $n-(k-l)$ is even. In an earlier paper, we proved that this is asymptotically optimal for all pair of integers $l<k$, i.e. $f(n,k,n-l)=(1+o(1))|\cF_0|$. In this paper we consider the case when $l=1$, $k\ge 2$, and prove that $f(n,k,n-1)=|\cF_0|$ provided $n$ is large enough. We also prove that the unique $(n-1)$-trace $k$-Sperner family with size $f(n,k,n-1)$ is $\cF_0$ and also $\cF&#39;_0$ when $n+k$ is odd.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Towards a de Bruijn-Erd\H os theorem in the $L_1$-metric

A well-known theorem of de Bruijn and Erdős states that any set of $n$ non-collinear points in the plane determines at least $n$ lines. Chen and Chvátal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of {\em betweenness}. In this paper, we prove that the answer is affirmative for sets of $n$ points in the plane with the $L_1$ metric, provided that no two points share their $x$- or $y$-coordinate. In this case, either there is a line that contains all $n$ points, or $X$ induces at least $n$ distinct lines. If points of $X$ are allowed to share their coordinates, then either there is a line that contains all $n$ points, or $X$ induces at least $n/37$ distinct lines.

0 citations0 reviewsNo code linkedOpen access