Máté Vizer
YOU?
Author Swipe
View article: The generalized trifference problem
The generalized trifference problem Open
We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ. For $m = 1$, this is the classical triffe…
View article: Counting connected partitions of graphs
Counting connected partitions of graphs Open
Motivated by the theorem of Győri and Lovász, we consider the following problem. For a connected graph on vertices and edges determine the number of unordered solutions of positive integers such that every is realized by a connected subgra…
View article: Extremal Graph Theoretic Questions for q-Ary Vectors
Extremal Graph Theoretic Questions for q-Ary Vectors Open
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 entries. The support of a q -edge $${\textbf{x}}$$ is …
View article: Generalized saturation game
Generalized saturation game Open
We study the following game version of the generalized graph Turán problem. For two fixed graphs F and H, two players, Max and Mini, alternately claim unclaimed edges of the complete graph Kn such that the graph G of the claimed edges must…
View article: Edge mappings of graphs: Ramsey type parameters
Edge mappings of graphs: Ramsey type parameters Open
In this paper, we address problems related to parameters concerning edge mappings of graphs. Inspired by Ramsey's Theorem, the quantity $m(G, H)$ is defined to be the minimum number $n$ such that for every $f: E(K_n) \rightarrow E(K_n)$ ei…
View article: Edge mappings of graphs: Turán type parameters
Edge mappings of graphs: Turán type parameters Open
In this paper, we address problems related to parameters concerning edge mappings of graphs. The quantity $h(n,G)$ is defined to be the maximum number of edges in an $n$-vertex graph $H$ such that there exists a mapping $f: E(H)\rightarrow…
View article: Improved Lower Bounds for Multiplicative Square-Free Sequences
Improved Lower Bounds for Multiplicative Square-Free Sequences Open
In this short paper we improve an almost 30 years old result of Erdős, Sárközy and Sós on lower bounds for the size of multiplicative square-free sequences. Our construction uses Berge-cycle free hypergraphs that is interesting in its own …
View article: The constructor-blocker game
The constructor-blocker game Open
Given two graphs F and H, Constructor and Blocker alternately claim unclaimed edges of the complete graph Kn. Constructor?s graph must remain F-free, while Blocker claims edges without restrictions. The game ends when Constructor cannot cl…
View article: Some exact results for regular Turán problems for all large orders
Some exact results for regular Turán problems for all large orders Open
As a variant of the famous Turán problem, we study rex(n,F), the maximum number of edges that an n-vertex regular graph can have without containing a copy of F. We determine rex(n,Kr+1) for all pairs of integers r and large enough n. For e…
View article: On graphs that contain exactly k copies of a subgraph, and a related problem in search theory
On graphs that contain exactly k copies of a subgraph, and a related problem in search theory Open
We study exak(n,F), the largest number of edges in an n-vertex graph that contains exactly k copies of a given subgraph F. The case k=0 is the Turán number ex(n,F) that is among the most studied parameters in extremal graph theory. We show…
View article: Vector sum-intersection theorems
Vector sum-intersection theorems Open
We introduce the following generalization of set intersection via characteristic vectors: for n,q,s,t≥1 a family F⊆{0,1,…,q}n of vectors is said to be s-sum t-intersecting if for any distinct x,y∈F there exist at least t coordinates, where…
View article: Extremal graph theoretic questions for q-ary vectors
Extremal graph theoretic questions for q-ary vectors Open
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 entries. The support of a $q$-edge $\mathbf{x}$ is the pair $S…
View article: The robust chromatic number of certain graph classes
The robust chromatic number of certain graph classes Open
A 1-selection $f$ of a graph $G$ is a function $f: V(G)\rightarrow 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)\setminus f[V(G)])$. The (1-)robust chromatic number $χ_1(G)$ is…
View article: The robust chromatic number of graphs
The robust chromatic number of graphs Open
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 \cup \{\varnothing\}$ is allowed to be non-injective), and $…
View article: Vector sum-intersection theorems
Vector sum-intersection theorems Open
We introduce the following generalization of set intersection via characteristic vectors: for $n,q,s, t \ge 1$ a family $\mathcal{F}\subseteq \{0,1,\dots,q\}^n$ of vectors is said to be \emph{$s$-sum $t$-intersecting} if for any distinct $…
View article: Counting Connected Partitions of Graphs
Counting Connected Partitions of Graphs Open
Motivated by the theorem of Gy\H ori and Lovász, we consider the following problem. For a connected graph $G$ on $n$ vertices and $m$ edges determine the number $P(G,k)$ of unordered solutions of positive integers $\sum_{i=1}^k m_i = m$ su…
View article: On graphs that contain exactly k copies of a subgraph, and a related problem in search theory
On graphs that contain exactly k copies of a subgraph, and a related problem in search theory Open
We study $\mathrm{exa}_k(n,F)$, the largest number of edges in an $n$-vertex graph $G$ that contains exactly $k$ copies of a given subgraph $F$. The case $k=0$ is the Turán number $\mathrm{ex}(n,F)$ that is among the most studied parameter…
View article: A plurality problem with three colors and query size three
A plurality problem with three colors and query size three Open
The Plurality problem - introduced by Aigner - has many variants. In this article we deal with the following version: suppose we are given n balls, each of them colored by one of three colors. A plurality ball is one such that its color cl…
View article: Saturation problems with regularity constraints
Saturation problems with regularity constraints Open
For a graph F, we say that another graph G is F-saturated, if G is F-free and adding any edge to G would create a copy of F. We study for a given graph F and integer n whether there exists a regular n-vertex F-saturated graph, and if it do…
View article: The Constructor-Blocker Game
The Constructor-Blocker Game Open
We study the following game version of the generalized graph Turán problem. For two fixed graphs $F$ and $H$, two players, Constructor and Blocker, alternately claim unclaimed edges of the complete graph $K_n$. Constructor can only claim e…
View article: On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs
On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs Open
For an integer $k \\geq 2$, an ordered $k$-uniform hypergraph\n$\\mathcal{H}=(H,<)$ is a $k$-uniform hypergraph $H$ together with a fixed\nlinear ordering $<$ of its vertex set. The ordered Ramsey number\n$\\overline{R}(\\mathcal{H},\\math…
View article: Rainbow Ramsey Problems for the Boolean Lattice
Rainbow Ramsey Problems for the Boolean Lattice Open
We address the following rainbow Ramsey problem: For posets P , Q what is the smallest number n such that any coloring of the elements of the Boolean lattice B n either admits a monochromatic copy of P or a rainbow copy of Q . We consider …
View article: Unified approach to the generalized Turán problem and supersaturation
Unified approach to the generalized Turán problem and supersaturation Open
In this paper we introduce a unifying approach to the generalized Turán problem and supersaturation results in graph theory. The supersaturation-extremal function satex(n,F:m,G) is the least number of copies of a subgraph G an n-vertex gra…
View article: On non-adaptive majority problems of large query size
On non-adaptive majority problems of large query size Open
We are given $n$ balls and an unknown coloring of them with two colors. Our goal is to find a ball that belongs to the larger color class, or show that the color classes have the same size. We can ask sets of $k$ balls as queries, and the …