Search

An internal or friendly partition of a vertex set $V(G)$ of a graph $G$ is a partition to two nonempty sets $A\cup B$ such that every vertex has at least as many neighbours in its own class as in the other one. Motivated by Diwan's existence proof on internal partitions of graphs with high girth, we give constructive proofs for the existence of internal partitions in the incidence graph of projective planes and discuss its geometric properties. In addition, we determine exactly the maximum possible difference between the sizes of the neighbor set in its own class and the neighbor set of the other class, that can be attained for all vertices at the same time for the incidence graphs of desarguesian planes of square order.

Let $G$ denote an Abelian group, written additively. A $3$-term arithmetic progression of $G$, $3$-$\mathrm{AP}$ for short, is a set of three distinct elements of $G$ of the form $g$, $g+d$, $g+2d$, for some $g,d \in G$. A set $S\subseteq G$ is called $3$-$\mathrm{AP}$ free if it does not contain a $3$-$\mathrm{AP}$. $S$ is called complete $3$-$\mathrm{AP}$ free if it is $3$-$\mathrm{AP}$ free and the addition of any further element would violate the $3$-$\mathrm{AP}$ free property. In case $S$ is not necessarily $3$-$\mathrm{AP}$ free but for each $x \in G \setminus S$ there is a $3$-$\mathrm{AP}$ of $G$ consisting of $x$ and two elements of $S$, we call $S$ saturating w.r.t. $3$-$\mathrm{AP}$s. A classical problem in additive combinatorics is to determine the maximal size of a $3$-$\mathrm{AP}$ free set. A classical problem in finite geometry and coding theory is to find the minimal size of a complete cap in affine spaces, where a cap is a point set without a collinear triplet and in $\mathbb{F}_3^n$ caps and $3$-$\mathrm{AP}$ free sets are the same objects. In this paper we determine the minimum size of complete $3$-$\mathrm{AP}$ free sets and $3$-$\mathrm{AP}$ saturating sets for several families of vector spaces and cyclic groups, up to a small multiplicative constant factor., Comment: Some typos are corrected, some new references are added

In order to reprove an old result of R\'edei's on the number of directions determined by a set of cardinality $p$ in $\mathbb{F}_p^2$, Somlai proved that the non-constant polynomials over the field $\mathbb{F}_p$ whose range sums are equal to $p$ are of degree at least $\frac{p-1}{2}$. Here we characterise all of these polynomials having degree exactly $\frac{p-1}{2}$, if $p$ is large enough. As a consequence, for the same set of primes we re-establish the characterisation of sets with few determined directions due to Lov\'asz and Schrijver using discrete Fourier analysis.

In a graph $G$, the $2$-neighborhood of a vertex set $X$ consists of all vertices of $G$ having at least $2$ neighbors in $X$. We say that a bipartite graph $G(A,B)$ satisfies the double Hall property if $|A|\geq2$, and every subset $X \subseteq A$ of size at least $2$ has a $2$-neighborhood of size at least $|X|$. Salia conjectured that any bipartite graph $G(A,B)$ satisfying the double Hall property contains a cycle covering $A$. Here, we prove the existence of a $2$-factor covering $A$ in any bipartite graph $G(A,B)$ satisfying the double Hall property. We also show Salia's conjecture for graphs with restricted degrees of vertices in $B$. Additionally, we prove a lower bound on the number of edges in a graph satisfying the double Hall property, and the bound is sharp up to a constant factor., Comment: minor corrections; to be published in Discrete Mathematics

We study the set of intersection sizes of a k-dimensional affine subspace and a point set of size m \in [0, 2^n] of the n-dimensional binary affine space AG(n,2). Following the theme of Erd\H{o}s, F\"uredi, Rothschild and T. S\'os, we partially determine which local densities in k-dimensional affine subspaces are unavoidable in all $m$-element point sets in the n-dimensional affine space. We also show constructions of point sets for which the intersection sizes with $k$-dimensional affine subspaces takes values from a set of a small size compared to 2^k. These are built up from affine subspaces and so-called subspace evasive sets. Meanwhile, we improve the best known upper bounds on subspace evasive sets and apply results concerning the canonical signed-digit (CSD) representation of numbers., Comment: some typos fixed, further reference added

The classical No-Three-In-Line problem seeks the maximum number of points that may be selected from an $n\times n$ grid while avoiding a collinear triple. The maximum is well known to be linear in $n$. Following a question of Erde, we seek to select sets of large density from the infinite grid $Z^{2}$ while avoiding a collinear triple. We show the existence of such a set which contains $\Theta(n/\log^{1+\varepsilon}n)$ points in $[1,n]^{2}$ for all $n$, where $\varepsilon>0$ is an arbitrarily small real number. We also give computational evidence suggesting that a set of lattice points may exist that has at least $n/2$ points on every large enough $n\times n$ grid., Comment: 12 pages, 3 figures

In this paper we continue the study of a natural generalization of Tur\'an's forbidden subgraph problem and the Ruzsa-Szemer\'edi problem. Let $ex_F(n,G)$ denote the maximum number of edge-disjoint copies of a fixed simple graph $F$ that can be placed on an $n$-vertex ground set without forming a subgraph $G$ whose edges are from different $F$-copies. The case when both $F$ and $G$ are triangles essentially gives back the theorem of Ruzsa and Szemer\'edi. We extend their results to the case when $F$ and $G$ are arbitrary cliques by applying a number theoretic result due to Erd\H{o}s, Frankl and R\"odl. This extension in turn decides the order of magnitude for a large family of graph pairs, which will be subquadratic, but almost quadratic. Since the linear $r$-uniform hypergraph Tur\'an problems to determine $ex_r^{lin}(n,G)$ form a class of the multicolor Tur\'an problem, following the identity $ex_r^{lin}(n,G)=ex_{K_r}(n,G)$, our results determine the linear hypergraph Tur\'an numbers of every graph of girth $3$ and for every $r$ up to a subpolynomial factor. Furthermore, when $G$ is a triangle, we settle the case $F=C_5$ and give bounds for the cases $F=C_{2k+1}$, $k\ge 3$ as well.

We consider a natural generalisation of Tur\'an's forbidden subgraph problem and the Ruzsa-Szemer\'edi problem by studying the maximum number $ex_F(n,G)$ of edge-disjoint copies of a fixed graph $F$ can be placed on an $n$-vertex ground set without forming a subgraph $G$ whose edges are from different $F$-copies. We determine the pairs $\{F, G\}$ for which the order of magnitude of $ex_F(n,G)$ is quadratic and prove several asymptotic results using various tools from the regularity lemma and supersaturation to graph packing results.

An internal or friendly partition of a graph is a partition of the vertex set into two nonempty sets so that every vertex has at least as many neighbours in its own class as in the other one. It has been shown that apart from finitely many counterexamples, every 3, 4 or 6-regular graph has an internal partition. In this note we focus on the $5$-regular case and show that among the subgraphs of minimum degree at least $3$, there are some which have small intersection. We also discuss the existence of internal partitions in some families of Cayley graphs, notably we determine all $5$-regular Abelian Cayley graphs which do not have an internal partition.

Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. In this paper we prove an upper bound on the minimal length of minimal codes of dimension $k$ over the $q$-element Galois field which is linear in both $q$ and $k$, hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well. The contributions rely on geometric and probabilistic arguments., Comment: Minor improvement for higgledy-piggledy line sets in the even order case. The main proof is slightly simplified. Some smaller mistakes are corrected

We address several extremal problems concerning the spreading property of point sets of Steiner triple systems. This property is closely related to the structure of subsystems, as a set is spreading if and only if there is no proper subsystem which contains it. We give sharp upper bounds on the size of a minimal spreading set in a Steiner triple system and show that if all the minimal spreading sets are large then the examined triple system must be a projective space. We also show that the size of a minimal spreading set is not an invariant of a Steiner triple system.

We prove an asymptotic result on the maximum number of k-vertex subtrees in binary trees of given order. This problem turns out to be equivalent to determine the maximum number of k+2-cycles in n-vertex outerplanar graphs, thus we settle the generalized outerplanar Tur\'an number for all cycles. We also determine the exponential growth of the generalized outerplanar Tur\'an number of paths Pk as a function of k which implies the order of magnitude of the generalized outerplanar Tur\'an number of arbitrary trees. The bounds are strongly related to the sequence of Catalan numbers.

In this paper we introduce a unifying approach to the generalized Tur\'an 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 graph can have, which contains at least $m$ copies of $F$ as a subgraph. We present a survey, discuss previously known results and obtain several new ones focusing mainly on proof methods, extremal structure and phase transition phenomena. Finally we point out some relation with extremal questions concerning hypergraphs, particularly Berge-type results., Comment: 16 pages

The long-standing Erd\H{o}s-Faber-Lov\'asz conjecture states that every $n$-uniform linear hypergaph with $n$ edges has a proper vertex-coloring using $n$ colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erd\H{o}s-Faber-Lov\'asz conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work.

The $r$-blowup of a graph $F$, denoted by $F[r]$, is the graph obtained by replacing the vertices and edges of $F$ with independent sets of size $r$ and copies of $K_{r,r}$, respectively. For bipartite graphs $F$, very little is known about the order of magnitude of the Tur\'an number of $F[r]$. In this paper we prove that $\mathrm{ex}(n,C_6[2])=O(n^{5/3})$ and, more generally, for any positive integer $t$, $\mathrm{ex}(n,\theta_{3,t}[2])=O(n^{5/3})$. This is tight when $t$ is sufficiently large., Comment: 14 pages; improved presentation

In this paper, we study vertex colorings of hypergraphs in which all color class sizes differ by at most one (balanced colorings) and each hyperedge contains at least two vertices of the same color (rainbow-free colorings). For any hypergraph $H$, the maximum number $k$ for which there is a balanced rainbow-free $k$-coloring of $H$ is called the balanced upper chromatic number of the hypergraph. We confirm the conjecture of Araujo-Pardo, Kiss and Montejano by determining the balanced upper chromatic number of the desarguesian projective plane $\mathrm{PG}(2,q)$ for all $q$. In addition, we determine asymptotically the balanced upper chromatic number of several families of non-desarguesian projective planes and also provide a general lower bound for arbitrary projective planes using probabilistic methods which determines the parameter up to a multiplicative constant.

The existence of Steiner triple systems STS(n) of order n containing no nontrivial subsystem is well known for every admissible n. We generalize this result in two ways. First we define the expander property of 3-uniform hypergraphs and show the existence of Steiner triple systems which are almost perfect expanders. Next we define the strong and weak spreading property of linear hypergraphs, and determine the minimum size of a linear triple system with these properties, up to a small constant factor. This property is strongly connected to the connectivity of the structure and of the so-called influence maximization. We also discuss how the results are related to Erd\H{o}s' conjecture on locally sparse STSs, influence maximization, subsquare-free Latin squares and possible applications in finite geometry., Comment: Some proofs are explained in a bit more details, one of the main theorems is stated in a precise form, and a minor mathematical error in Prop 3.3 is corrected

A conjecture of Erd\H{o}s from 1967 asserts that any graph on $n$ vertices which does not contain a fixed $r$-degenerate bipartite graph $F$ has at most $Cn^{2-1/r}$ edges, where $C$ is a constant depending only on $F$. We show that this bound holds for a large family of $r$-degenerate bipartite graphs, including all $r$-degenerate blow-ups of trees. Our results generalise many previously proven cases of the Erd\H{o}s conjecture, including the related results of F\"uredi and Alon, Krivelevich and Sudakov. Our proof uses supersaturation and a random walk on an auxiliary graph.

A widely investigated subject in combinatorial geometry, originated from Erd\H{o}s, is the following. Given a point set $P$ of cardinality $n$ in the plane, how can we describe the distribution of the determined distances? This has been generalized in many directions. In this paper we propose the following variants. Consider planar arrangements of $n$ lines. Determine the maximum number of triangles of unit area, maximum area or minimum area, determined by these lines. Determine the minimum size of a subset of these $n$ lines so that all triples determine distinct area triangles. We prove that the order of magnitude for the maximum occurrence of unit areas lies between $\Omega(n^2)$ and $O(n^{9/4})$. This result is strongly connected to both additive combinatorial results and Szemer\'edi--Trotter type incidence theorems. Next we show a tight bound for the maximum number of minimum area triangles. Finally we present lower and upper bounds for the maximum area and distinct area problems by combining algebraic, geometric and combinatorial techniques., Comment: Title is shortened. Some typos and small errors were corrected

For a positive integer $n$, a graph $F$ and a bipartite graph $G\subseteq K_{n,n}$ let ${F(n+n, G)}$ denote the number of copies of $F$ in $G$, and let $F(n+n, m)$ denote the minimum number of copies of $F$ in all graphs $G\subseteq K_{n,n}$ with $m$ edges. The study of such a function is the subject of theorems of supersaturated graphs and closely related to the Sidorenko-Erd\H{o}s-Simonovits conjecture as well. In the present paper we investigate the case when $F= K_{2,t}$ and in particular the quadrilateral graph case. For $F=C_4$, we obtain exact results if $m$ and the corresponding Zarankiewicz number differ by at most $n$, by a finite geometric construction of almost difference sets. $F= K_{2,t}$ if $m$ and the corresponding Zarankiewicz number differs by $Cn\sqrt{n}$ we prove asymptotically sharp results. We also study stability questions and point out the connections to covering and packing block designs.

We consider the so-called coupon-coloring of the vertices of a graph where every color appears in every open neighborhood, and our aim is to determine the maximal number of colors in such colorings. In other words, every color class must be a total dominating set in the graph and we study the total domatic number of the graph. We determine this parameter in every maximal outerplanar graph, and show that every Hamiltonian maximal planar graph has domatic number at least two, partially answering a conjecture of Goddard and Henning.

We are seeking a sufficient condition that forces a transversal in a generalized Latin square. A generalized Latin square of order $n$ is equivalent to a proper edge-coloring of $K_{n,n}$. A transversal corresponds to a multicolored perfect matching. Akbari and Alipour defined $l(n)$ as the least integer such that every properly edge-colored $K_{n,n}$, which contains at least $l(n)$ different colors, admits a multicolored perfect matching. They conjectured that $l(n)\leq n^2/2$ if $n$ is large enough. In this note we prove that $l(n)$ is bounded from above by $0.75n^2$ if $n>1$. We point out a connection to anti-Ramsey problems. We propose a conjecture related to a well-known result by Woolbright and Fu, that every proper edge-coloring of $K_{2n}$ admits a multicolored $1$-factor.

Let $\Pi_q$ be an arbitrary finite projective plane of order $q$. A subset $S$ of its points is called saturating if any point outside $S$ is collinear with a pair of points from $S$. Applying probabilistic tools we improve the upper bound on the smallest possible size of the saturating set to $\lceil\sqrt{3q\ln{q}}\rceil+ \lceil(\sqrt{q}+1)/2\rceil$. The same result is presented using an algorithmic approach as well, which points out the connection with the transversal number of uniform multiple intersecting hypergraphs., Comment: 10 pages, detailed calculations are included compared to V1

We determine the partition dimension of the incidence graph $G(\Pi_q)$ of the projective plane $\Pi_q$ up to a constant factor $2$ as $(2+o(1))\log_2{q}\leq \mathrm{pd}(G(\Pi_q))\leq (4+o(1))\log_2{q}.$, Comment: 11 pages

We describe small dominating sets of the incidence graphs of finite projective planes by establishing a stability result which shows that dominating sets are strongly related to blocking and covering sets. Our main result states that if a dominating set in a projective plane of order $q>81$ is smaller than $2q+2[\sqrt{q}]+2$ (i.e., twice the size of a Baer subplane), then it contains either all but possibly one points of a line or all but possibly one lines through a point. Furthermore, we completely characterize dominating sets of size at most $2q+\sqrt{q}+1$. In Desarguesian planes, we could rely on strong stability results on blocking sets to show that if a dominating set is sufficiently smaller than 3q, then it consists of the union of a blocking set and a covering set apart from a few points and lines., Comment: 19 pages

We study the existence and the number of $k$-dominating independent sets in certain graph families. While the case $k=1$ namely the case of maximal independent sets - which is originated from Erd\H{o}s and Moser - is widely investigated, much less is known in general. In this paper we settle the question for trees and prove that the maximum number of $k$-dominating independent sets in $n$-vertex graphs is between $c_k\cdot\sqrt[2k]{2}^n$ and $c_k'\cdot\sqrt[k+1]{2}^n$ if $k\geq 2$, moreover the maximum number of $2$-dominating independent sets in $n$-vertex graphs is between $c\cdot 1.22^n$ and $c'\cdot1.246^n$. Graph constructions containing a large number of $k$-dominating independent sets are coming from product graphs, complete bipartite graphs and with finite geometries. The product graph construction is associated with the number of certain MDS codes., Comment: 13 pages

We study the function $M(n,k)$ which denotes the number of maximal $k$-uniform intersecting families $F\subseteq \binom{[n]}{k}$. Improving a bound of Balogh at al. on $M(n,k)$, we determine the order of magnitude of $\log M(n,k)$ by proving that for any fixed $k$, $M(n,k) =n^{\Theta(\binom{2k}{k})}$ holds. Our proof is based on Tuza's set pair approach. The main idea is to bound the size of the largest possible point set of a cross-intersecting system. We also introduce and investigate some related functions and parameters., Comment: 11 pages

Let $H$ be a graph on $n$ vertices and let the blow-up graph $G[H]$ be defined as follows. We replace each vertex $v_i$ of $H$ by a cluster $A_i$ and connect some pairs of vertices of $A_i$ and $A_j$ if $(v_i,v_j)$ was an edge of the graph $H$. As usual, we define the edge density between $A_i$ and $A_j$ as $d(A_i,A_j)=\frac{e(A_i,A_j)}{|A_i||A_j|}.$ We study the following problem. Given densities $\gamma_{ij}$ for each edge $(i,j)\in E(H)$. Then one has to decide whether there exists a blow-up graph $G[H]$ with edge densities at least $\gamma_{ij}$ such that one cannot choose a vertex from each cluster so that the obtained graph is isomorphic to $H$, i.e, no $H$ appears as a transversal in $G[H]$. We call $d_{crit}(H)$ the maximal value for which there exists a blow-up graph $G[H]$ with edge densities $d(A_i,A_j)=d_{crit}(H)$ $((v_i,v_j)\in E(H))$ not containing $H$ in the above sense. Our main goal is to determine the critical edge density and to characterize the extremal 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\'enyi random graphs and graphs of bounded maximum degree .

We discuss a variant of the Ramsey and the directed Ramsey problem. First, consider a complete graph on $n$ vertices and a two-coloring of the edges such that every edge is colored with at least one color and the number of bicolored edges $|E_{RB}|$ is given. The aim is to find the maximal size $f$ of a monochromatic clique which is guaranteed by such a coloring. Analogously, in the second problem we consider semicomplete digraph on $n$ vertices such that the number of bi-oriented edges $|E_{bi}|$ is given. The aim is to bound the size $F$ of the maximal transitive subtournament that is guaranteed by such a digraph. Applying probabilistic and analytic tools and constructive methods we show that if $|E_{RB}|=|E_{bi}| = p{n\choose 2}$, ($p\in [0,1)$), then $f, F < C_p\log(n)$ where $C_p$ only depend on $p$, while if $m={n \choose 2} - |E_{RB}|

Selberg-type integrals that can be turned into constant term identities for Laurent polynomials arise naturally in conjunction with random matrix models in statistical mechanics. Built on a recent idea of Karasev and Petrov we develop a general interpolation based method that is powerful enough to establish many such identities in a simple manner. The main consequence is the proof of a conjecture of Forrester related to the Calogero--Sutherland model. In fact we prove a more general theorem, which includes Aomoto's constant term identity at the same time. We also demonstrate the relevance of the method in additive combinatorics., Comment: 21 pages

In this paper, we study $(1 : b)$ Avoider-Enforcer games played on the edge set of the complete graph on $n$ vertices. For every constant $k\geq 3$ we analyse the $k$-star game, where Avoider tries to avoid claiming $k$ edges incident to the same vertex. We analyse both versions of Avoider-Enforcer games -- the strict and the monotone -- and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases $f^{mon}_\mathcal{F}$, $f^-_\mathcal{F}$ and $f^+_\mathcal{F}$, where $\mathcal{F}$ is the hypergraph of the game.

Generalizing a result in the theory of finite fields we prove that, apart from a couple of exceptions that can be classified, for any elements $a_1,...,a_m$ of the cyclic group of order $m$, there is a permutation $\pi$ such that $1a_{\pi(1)}+...+ma_{\pi(m)}=0$.

As an application of the Combinatorial Nullstellensatz, we give a short polynomial proof of the q-analogue of Dyson's conjecture formulated by Andrews and first proved by Zeilberger and Bressoud.

To study how balanced or unbalanced a maximal intersecting family $\mathcal{F}\subseteq \binom{[n]}{r}$ is we consider the ratio $\mathcal{R}(\mathcal{F})=\frac{\Delta(\mathcal{F})}{\delta(\mathcal{F})}$ of its maximum and minimum degree. We determine the order of magnitude of the function $m(n,r)$, the minimum possible value of $\mathcal{R}(\mathcal{F})$, and establish some lower and upper bounds on the function $M(n,r)$, the maximum possible value of $\mathcal{R}(\mathcal{F})$. To obtain constructions that show the bounds on $m(n,r)$ we use a theorem of Blokhuis on the minimum size of a non-trivial blocking set in projective planes.