Bal'azs Patk'os

collaborators

7 papers

math.CO2023

Query complexity of Boolean functions on the middle slice of the cube

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4

We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to co…

math.CO2023

On some extremal and probabilistic questions for tree posets

Balázs Patkós, Andrew Treglown

Given two posets $P, Q$ we say that $Q$ is $P$ -free if $Q$ does not contain a copy of $P$ . The size of the largest $P$ -free family in $2^{[n]}$ , denoted by $L a (n, P)$ , has been exten…

math.CO2023

The robust chromatic number of certain graph classes

Gábor Bacsó, Csilla Bujtás, Balázs Patkós +2

A 1-selection $f$ of a graph $G$ is a function $f : V (G) \to E (G)$ such that $f (v)$ is incident to $v$ for every vertex $v$ . The 1-removed $G_{f}$ is the graph $(V(G),E(G)\setm…

math.CO2023

The robust chromatic number of graphs

Gábor Bacsó, Balázs Patkós, Zsolt Tuza +1

A 1-removed subgraph $G_{f}$ of a graph $G = (V, E)$ is obtained by $(i)$ selecting at most one edge $f (v)$ for each vertex $v \in V$ , such that $v \in f (v) \in E$ (the mapping $f:V\to E \…

math.CO2023

Extremal graph theoretic questions for q-ary vectors

Balázs Patkós, Zsolt Tuza, Máté Vizer

A $q$ -graph $H$ on $n$ vertices is a set of vectors of length $n$ with all entries from ${0, 1, \dots, q}$ and every vector (that we call a $q$ -edge) having exactly two non-zero ent…

math.CO2023

Vector sum-intersection theorems

Balázs Patkós, Zsolt Tuza, Máté Vizer

We introduce the following generalization of set intersection via characteristic vectors: for $n, q, s, t \geq 1$ a family $F \subseteq {0, 1, \dots, q}^{n}$ of vectors is said…