Source author record

Peter Borg

Peter Borg appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

What is connected

16works

2topics

3close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2025arXiv

Solution to a problem on isolation of cliques in uniform hypergraphs

A copy of a hypergraph $F$ is called an $F$-copy. Let $K_k^r$ denote the complete $r$-uniform hypergraph whose vertex set is $[k] = \{1, \dots, k\}$ (that is, the edges of $K_k^r$ are the $r$-element subsets of $[k]$). Given an $r$-uniform $n$-vertex hypergraph $H$, the $K_k^r$-isolation number of $H$, denoted by $ι(H, K_k^r)$, is the size of a smallest subset $D$ of the vertex set of $H$ such that the closed neighbourhood $N[D]$ of $D$ intersects the vertex sets of the $K_k^r$-copies contained by $H$ (equivalently, $H-N[D]$ contains no $K_k^r$-copy). In this note, we show that if $2 \leq r \leq k$ and $H$ is connected, then $ι(H, K_k^r) \leq \frac{n}{k+1}$ unless $H$ is a $K_k^r$-copy or $k = r = 2$ and $H$ is a $5$-cycle. This solves a recent problem of Li, Zhang and Ye. The result for $r = 2$ (that is, $H$ is a graph) was proved by Fenech, Kaemawichanurat and the author, and is used to prove the result for any $r$. The extremal structures for $r = 2$ were determined by various authors. We use this to determine the extremal structures for any $r$.

preprint2023arXiv

Solution to a problem of Katona on counting cliques of weighted graphs

A subset $I$ of the vertex set $V(G)$ of a graph $G$ is called a $k$-clique independent set of $G$ if no $k$ vertices in $I$ form a $k$-clique of $G$. An independent set is a $2$-clique independent set. Let $π_k(G)$ denote the number of $k$-cliques of $G$. For a function $w: V(G) \rightarrow \{0, 1, 2, \dots\}$, let $G(w)$ be the graph obtained from $G$ by replacing each vertex $v$ by a $w(v)$-clique $K^v$ and making each vertex of $K^u$ adjacent to each vertex of $K^v$ for each edge $\{u,v\}$ of $G$. For an integer $m \geq 1$, consider any $w$ with $\sum_{v \in V(G)} w(v) = m$. For $U \subseteq V(G)$, we say that $w$ is uniform on $U$ if $w(v) = 0$ for each $v \in V(G) \setminus U$ and, for each $u \in U$, $w(u) = \left\lfloor m/|U| \right\rfloor$ or $w(u) = \left\lceil m/|U| \right\rceil$. Katona asked if $π_k(G(w))$ is smallest when $w$ is uniform on a largest $k$-clique independent set of $G$. He placed particular emphasis on the Sperner graph $B_n$, given by $V(B_n) = \{X \colon X \subseteq \{1, \dots, n\}\}$ and $E(B_n) = \{\{X,Y\} \colon X \subsetneq Y \in V(B_n)\}$. He provided an affirmative answer for $k = 2$ (and any $G$). We determine graphs for which the answer is negative for every $k \geq 3$. These include $B_n$ for $n \geq 2$. Generalizing Sperner's Theorem and a recent result of Qian, Engel and Xu, we show that $π_k(B_n(w))$ is smallest when $w$ is uniform on a largest independent set of $B_n$. We also show that the same holds for complete multipartite graphs and chordal graphs. We show that this is not true of every graph, using a deep result of Bohman on triangle-free graphs.

preprint2021arXiv

The maximum sum of sizes of cross-intersecting families of subsets of a set

A set of sets is called a family. Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-intersecting if each member of $\mathcal{A}$ intersects each member of $\mathcal{B}$. For any two integers $n$ and $k$ with $1 \leq k \leq n$, let ${[n] \choose \leq k}$ denote the family of subsets of $[n] = \{1, \dots, n\}$ that have at most $k$ elements. We show that if $\mathcal{A}$ is a non-empty subfamily of ${[n] \choose \leq r}$, $\mathcal{B}$ is a non-empty subfamily of ${[n] \choose \leq s}$, $r \leq s$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then \[|\mathcal{A}| + |\mathcal{B}| \leq 1 + \sum_{i=1}^s \left({n \choose i} - {n-r \choose i} \right),\] and equality holds if $\mathcal{A} = \{[r]\}$ and $\mathcal{B}$ is the family of sets in ${[n] \choose \leq s}$ that intersect $[r]$.

preprint2020arXiv

Reducing the maximum degree of a graph: comparisons of bounds

Let $λ(G)$ be the smallest number of vertices that can be removed from a non-empty graph $G$ so that the resulting graph has a smaller maximum degree. Let $λ_{\rm e}(G)$ be the smallest number of edges that can be removed from $G$ for the same purpose. Let $k$ be the maximum degree of $G$, let $t$ be the number of vertices of degree $k$, let $M(G)$ be the set of vertices of degree $k$, let $n$ be the number of vertices in the closed neighbourhood of $M(G)$, and let $m$ be the number of edges incident to vertices in $M(G)$. Fenech and the author showed that $λ(G) \leq \frac{n+(k-1)t}{2k}$, and they essentially showed that $λ(G) \leq n \left ( 1- \frac{k}{k+1} { \Big( \frac{n}{(k+1)t} \Big) }^{1/k} \right )$. They also showed that $λ_{\rm e}(G) \leq \frac{m + (k-1)t}{2k-1}$ and $λ_{\rm e} (G) \leq m \left ( 1- \frac{k-1}{k} { \Big( \frac{m}{kt} \Big) }^{1/(k-1)} \right )$. These bounds are attained if $k \geq 2$ and $G$ is the union of $t$ pairwise vertex-disjoint $(k+1)$-vertex stars. For each of $λ(G)$ and $λ_{\rm e}(G)$, the two bounds on the parameter are compared for the purpose of determining, for each bound, the cases in which the bound is better than the other. This work is also motivated by the likelihood that similar pairs of bounds will be discovered for other graph parameters and the same analysis can be applied.

preprint2016arXiv

Stars on trees

For a positive integer $r$ and a vertex $v$ of a graph $G$, let $\mathcal{I}_G^{(r)}(v)$ denote the set of all independent sets of $G$ that have exactly $r$ elements and contain $v$. Hurlbert and Kamat conjectured that for any $r$ and any tree $T$, there exists a leaf $z$ of $T$ such that $|\mathcal{I}_T^{(r)}(v)| \leq |\mathcal{I}_T^{(r)}(z)|$ for each vertex $v$ of $T$. They proved the conjecture for $r \leq 4$. For any $k \geq 3$, we construct a tree $T_k$ that has a vertex $x$ such that $x$ is not a leaf of $T_k$, $|\mathcal{I}_{T_k}^{(r)}(z)| < |\mathcal{I}_{T_k}^{(r)}(x)|$ for any leaf $z$ of $T_k$ and any $5 \leq r \leq 2k+1$, and $2k+1$ is the largest integer $s$ for which $\mathcal{I}_{T_k}^{(s)}(x)$ is non-empty. Therefore, the conjecture is not true for $r \geq 5$.

preprint2016arXiv

The maximum product of sizes of cross-intersecting families

We say that a set $A$ $t$-intersects a set $B$ if $A$ and $B$ have at least $t$ common elements. Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-$t$-intersecting if each set in $\mathcal{A}$ $t$-intersects each set in $\mathcal{B}$. A subfamily $\mathcal{S}$ of a family $\mathcal{F}$ is called a $t$-star of $\mathcal{F}$ if the sets in $\mathcal{S}$ have $t$ common elements. Let $l(\mathcal{F},t)$ denote the size of a largest $t$-star of $\mathcal{F}$. We call $\mathcal{F}$ a $(\leq r)$-family if each set in $\mathcal{F}$ has at most $r$ elements. We determine a function $c : \mathbb{N}^3 \rightarrow \mathbb{N}$ such that the following holds. If $\mathcal{A}$ is a subfamily of a $(\leq r)$-family $\mathcal{F}$ with $l(\mathcal{F},t) \geq c(r,s,t)l(\mathcal{F},t+1)$, $\mathcal{B}$ is a subfamily of a $(\leq s)$-family $\mathcal{G}$ with $l(\mathcal{G},t) \geq c(r,s,t)l(\mathcal{G},t+1)$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-$t$-intersecting, then $|\mathcal{A}||\mathcal{B}| \leq l(\mathcal{F},t)l(\mathcal{G},t)$. Some known results follow from this, and we identify several natural classes of families for which the bound is attained.

preprint2015arXiv

The maximum product of weights of cross-intersecting families

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-$t$-intersecting if each set in $\mathcal{A}$ intersects each set in $\mathcal{B}$ in at least $t$ elements. An active problem in extremal set theory is to determine the maximum product of sizes of cross-$t$-intersecting subfamilies of a given family. We prove a cross-$t$-intersection theorem for weighted subsets of a set by means of a new subfamily alteration method, and use the result to provide solutions for three natural families. For $r\in[n]=\{1,2,\dots,n\}$, let ${[n]\choose r}$ be the family of $r$-element subsets of $[n]$, and let ${[n]\choose\leq r}$ be the family of subsets of $[n]$ that have at most $r$ elements. Let $\mathcal{F}_{n,r,t}$ be the family of sets in ${[n]\choose\leq r}$ that contain $[t]$. We show that if $g:{[m]\choose\leq r}\rightarrow\mathbb{R}^+$ and $h:{[n]\choose\leq s}\rightarrow\mathbb{R}^+$ are functions that obey certain conditions, $\mathcal{A}\subseteq{[m]\choose\leq r}$, $\mathcal{B}\subseteq{[n]\choose\leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-$t$-intersecting, then \[\sum_{A\in\mathcal{A}}g(A)\sum_{B\in\mathcal{B}}h(B)\leq\sum_{C\in\mathcal{F}_{m,r,t}}g(C)\sum_{D\in\mathcal{F}_{n,s,t}}h(D),\] and equality holds if $\mathcal{A}=\mathcal{F}_{m,r,t}$ and $\mathcal{B}=\mathcal{F}_{n,s,t}$. We prove this in a more general setting and characterise the cases of equality. We use the result to show that the maximum product of sizes of two cross-$t$-intersecting families $\mathcal{A}\subseteq{[m]\choose r}$ and $\mathcal{B}\subseteq{[n]\choose s}$ is ${m-t\choose r-t}{n-t\choose s-t}$ for $\min\{m,n\}\geq n_0(r,s,t)$, where $n_0(r,s,t)$ is close to best possible. We obtain analogous results for families of integer sequences and for families of multisets. The results yield generalisations for $k\geq2$ cross-$t$-intersecting families, and Erdos-Ko-Rado-type results.

preprint2014arXiv

A cross-intersection theorem for subsets of a set

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-intersecting if each member of $\mathcal{A}$ intersects each member of $\mathcal{B}$. For any two integers $n$ and $k$ with $0 \leq k \leq n$, let ${[n] \choose \leq k}$ denote the family of all subsets of $\{1, \dots, n\}$ of size at most $k$. We show that if $\mathcal{A} \subseteq {[m] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then \[|\mathcal{A}||\mathcal{B}| \leq \sum_{i=0}^r {m-1 \choose i-1} \sum_{j=0}^s {n-1 \choose j-1},\] and equality holds if $\mathcal{A} = \{A \in {[m] \choose \leq r} \colon 1 \in A\}$ and $\mathcal{B} = \{B \in {[n] \choose \leq s} \colon 1 \in B\}$. Also, we generalise this to any number of such cross-intersecting families.

preprint2014arXiv

Cross-intersecting integer sequences

We call $(a_1, \dots, a_n)$ an \emph{$r$-partial sequence} if exactly $r$ of its entries are positive integers and the rest are all zero. For ${\bf c} = (c_1, \dots, c_n)$ with $1 \leq c_1 \leq \dots \leq c_n$, let $S_{\bf c}^{(r)}$ be the set of $r$-partial sequences $(a_1, \dots, a_n)$ with $0 \leq a_i \leq c_i$ for each $i$ in $\{1, \dots, n\}$, and let $S_{\bf c}^{(r)}(1)$ be the set of members of $S_{\bf c}^{(r)}$ which have $a_1 = 1$. We say that $(a_1, \dots, a_n)$ \emph{meets} $(b_1, \dots, b_m)$ if $a_i = b_i \neq 0$ for some $i$. Two sets $A$ and $B$ of sequences are said to be \emph{cross-intersecting} if each sequence in $A$ meets each sequence in $B$. Let ${\bf d} = (d_1, \dots, d_m)$ with $1 \leq d_1 \leq \dots \leq d_m$. Let $A \subseteq S_{\bf c}^{(r)}$ and $B \subseteq S_{\bf d}^{(s)}$ such that $A$ and $B$ are cross-intersecting. We show that $|A||B| \leq |S_{\bf c}^{(r)}(1)||S_{\bf d}^{(s)}(1)|$ if either $c_1 \geq 3$ and $d_1 \geq 3$ or ${\bf c} = {\bf d}$ and $r = s = n$. We also determine the cases of equality. We obtain this by proving a general cross-intersection theorem for \emph{weighted} sets. The bound generalises to one for $k \geq 2$ cross-intersecting sets.

preprint2014arXiv

Intersecting generalised permutations

For any positive integers $k,r,n$ with $r \leq \min\{k,n\}$, let $\mathcal{P}_{k,r,n}$ be the family of all sets $\{(x_1,y_1), \dots, (x_r,y_r)\}$ such that $x_1, \dots, x_r$ are distinct elements of $[k] = \{1, \dots, k\}$ and $y_1, \dots, y_r$ are distinct elements of $[n]$. The families $\mathcal{P}_{n,n,n}$ and $\mathcal{P}_{n,r,n}$ describe permutations of $[n]$ and $r$-partial permutations of $[n]$, respectively. If $k \leq n$, then $\mathcal{P}_{k,k,n}$ describes permutations of $k$-element subsets of $[n]$. A family $\mathcal{A}$ of sets is said to be intersecting if every two members of $\mathcal{A}$ intersect. In this note we use Katona's elegant cycle method to show that a number of important Erdős-Ko-Rado-type results by various authors generalise as follows: the size of any intersecting subfamily $\mathcal{A}$ of $\mathcal{P}_{k,r,n}$ is at most ${k-1 \choose r-1}\frac{(n-1)!}{(n-r)!}$, and the bound is attained if and only if $\mathcal{A} = \{A \in \mathcal{P}_{k,r,n} \colon (a,b) \in A\}$ for some $a \in [k]$ and $b \in [n]$.

preprint2013arXiv

A sharp upper bound for the independence number

An $r$-graph $G$ is a pair $(V,E)$ such that $V$ is a set and $E$ is a family of $r$-element subsets of $V$. The \emph{independence number} $α(G)$ of $G$ is the size of a largest subset $I$ of $V$ such that no member of $E$ is a subset of $I$. The \emph{transversal number} $τ(G)$ of $G$ is the size of a smallest subset $T$ of $V$ that intersects each member of $E$. $G$ is said to be \emph{connected} if for every distinct $v$ and $w$ in $V$ there exists a \emph{path} from $v$ to $w$ (that is, a sequence $e_1, \dots, e_p$ of members of $E$ such that $v \in e_1$, $w \in e_p$, and if $p \geq 2$, then for each $i \in \{1, \dots, p-1\}$, $e_i$ intersects $e_{i+1}$). The \emph{degree} of a member $v$ of $V$ is the number of members of $E$ that contain $v$. The maximum of the degrees of the members of $V$ is denoted by $Δ(G)$. We show that for any $1 \leq k < n$, if $G = (V,E)$ is a connected $r$-graph, $|V| = n$, and $Δ(G) = k$, then \[α(G) \leq n - \left \lceil \frac{n-1}{k(r-1)} \right \rceil, \quad τ(G) \geq \left \lceil \frac{n-1}{k(r-1)} \right \rceil,\] and these bounds are sharp. The two bounds are equivalent.

preprint2013arXiv

Intersecting integer partitions

If $a_1, a_2, ..., a_k$ and $n$ are positive integers such that $n = a_1 + a_2 + ... + a_k$, then the sum $a_1 + a_2 + ... + a_k$ is said to be a \emph{partition of $n$} of \emph{length $k$}, and $a_1, a_2, ..., a_k$ are said to be the \emph{parts} of the partition. Two partitions that differ only in the order of their parts are considered to be the same. We say that two partitions \emph{intersect} if they have at least one common part. We call a set $A$ of partitions \emph{intersecting} if any two partitions in $A$ intersect. Let $P_{n,k}$ be the set of all partitions of $n$ of length $k$. We conjecture that if $2 \leq k \leq n$, then the size of any intersecting subset of $P_{n,k}$ is at most the size of $P_{n-1,k-1}$, which is the size of the intersecting subset of $P_{n,k}$ consisting of those partitions which have 1 as a part. The conjecture is trivially true for $n \leq 2k$, and we prove it for $n \geq 5k^5$. We also generalise this for subsets of $P_{n,k}$ with the property that any two of their members have at least $t$ common parts.

preprint2013arXiv

The maximum product of sizes of cross-$t$-intersecting uniform families

We say that a set $A$ \emph{$t$-intersects} a set $B$ if $A$ and $B$ have at least $t$ common elements. Two families $\mathcal{A}$ and $\mathcal{B}$ are said to be \emph{cross-$t$-intersecting} if each set in $\mathcal{A}$ $t$-intersects each set in $\mathcal{B}$. For any positive integers $n$ and $r$, let ${[n] \choose r}$ denote the family of all $r$-element subsets of $\{1,2,\dots, n\}$. We show that for any integers $r$, $s$ and $t$ with $1 \leq t \leq r \leq s$, there exists an integer $n_0(r,s,t)$ such that for any integer $n \geq n_0(r,s,t)$, if $\mathcal{A} \subset {[n] \choose r}$ and $\mathcal{B} \subset {[n] \choose s}$ such that $\mathcal{A}$ and $\mathcal{B}$ are cross-$t$-intersecting, then $|\mathcal{A}||\mathcal{B}| \leq {n-t \choose r-t}{n-t \choose s-t}$, and equality holds if and only if for some $T \in {[n] \choose t}$, $\mathcal{A} = \{A \in {[n] \choose r} \colon T \subset A\}$ and $\mathcal{B} = \{B \in {[n] \choose s} \colon T \subset B\}$. This verifies a conjecture of Hirschorn.

preprint2012arXiv

The maximum sum and maximum product of sizes of cross-intersecting families

We say that a set $A$ \emph{$t$-intersects} a set $B$ if $A$ and $B$ have at least $t$ common elements. A family $\mathcal{A}$ of sets is said to be \emph{$t$-intersecting} if each set in $\mathcal{A}$ $t$-intersects any other set in $\mathcal{A}$. Families $\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k$ are said to be \emph{cross-$t$-intersecting} if for any $i$ and $j$ in $\{1, 2, ..., k\}$ with $i \neq j$, any set in $\mathcal{A}_i$ $t$-intersects any set in $\mathcal{A}_j$. We prove that for any finite family $\mathcal{F}$ that has at least one set of size at least $t$, there exists an integer $κ\leq |\mathcal{F}|$ such that for any $k \geq κ$, both the sum and the product of sizes of any $k$ cross-$t$-intersecting sub-families $\mathcal{A}_1, ..., \mathcal{A}_k$ (not necessarily distinct or non-empty) of $\mathcal{F}$ are maxima if $\mathcal{A}_1 = ... = \mathcal{A}_k = \mathcal{L}$ for some largest $t$-intersecting sub-family $\mathcal{L}$ of $\mathcal{F}$. We then study the smallest possible value of $κ$ and investigate the case $k < κ$; this includes a cross-intersection result for straight lines that demonstrates that it is possible to have $\mathcal{F}$ and $κ$ such that for any $k < κ$, the configuration $\mathcal{A}_1 = ... = \mathcal{A}_k = \mathcal{L}$ is neither optimal for the sum nor optimal for the product. We also outline solutions for various important families $\mathcal{F}$, and we provide solutions for the case when $\mathcal{F}$ is a power set.

preprint2011arXiv

Cross-intersecting sub-families of hereditary families

Families $\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k$ of sets are said to be \emph{cross-intersecting} if for any $i$ and $j$ in $\{1, 2, ..., k\}$ with $i \neq j$, any set in $\mathcal{A}_i$ intersects any set in $\mathcal{A}_j$. For a finite set $X$, let $2^X$ denote the \emph{power set of $X$} (the family of all subsets of $X$). A family $\mathcal{H}$ is said to be \emph{hereditary} if all subsets of any set in $\mathcal{H}$ are in $\mathcal{H}$; so $\mathcal{H}$ is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family $\mathcal{H} \neq \{\emptyset\}$ of $2^X$ and any $k \geq |X|+1$, both the sum and product of sizes of $k$ cross-intersecting sub-families $\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k$ (not necessarily distinct or non-empty) of $\mathcal{H}$ are maxima if $\mathcal{A}_1 = \mathcal{A}_2 = ... = \mathcal{A}_k = \mathcal{S}$ for some largest \emph{star $\mathcal{S}$ of $\mathcal{H}$} (a sub-family of $\mathcal{H}$ whose sets have a common element). We prove this for the case when $\mathcal{H}$ is \emph{compressed with respect to an element $x$ of $X$}, and for this purpose we establish new properties of the usual \emph{compression operation}. For the product, we actually conjecture that the configuration $\mathcal{A}_1 = \mathcal{A}_2 = ... = \mathcal{A}_k = \mathcal{S}$ is optimal for any hereditary $\mathcal{H}$ and any $k \geq 2$, and we prove this for a special case too.

preprint2011arXiv

Intersecting families of sets and permutations: a survey

A family $\mathcal{A}$ of sets is said to be \emph{$t$-intersecting} if any two sets in $\mathcal{A}$ have at least $t$ common elements. A central problem in extremal set theory is to determine the size or structure of a largest $t$-intersecting sub-family of a given family $\mathcal{F}$. We give a survey of known results, conjectures and open problems for various important families $\mathcal{F}$, namely, power sets, levels of power sets, hereditary families, families of signed sets, families of labeled sets, and families of permutations. We also provide some extensions and consequences of known results.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint