BZPEER

preprint2022arXiv

Approximately Strongly Regular Graphs

We give variants of the Krein bound and the absolute bound for graphs with a spectrum similar to that of a strongly regular graph. In particular, we investigate what we call approximately strongly regular graphs. We apply our results to extremal problems. Among other things, we show the following: (1) Caps in $\mathrm{PG}(n, q)$ for which the number of secants on exterior points does not vary too much, have size at most $O(q^{\frac34 n})$ (as $q \rightarrow \infty$ or as $n \rightarrow \infty$ ). (2) Optimally pseudorandom $K_m$ -free graphs of order $v$ and degree $k$ for which the induced subgraph on the common neighborhood of a clique of size $i \leq m-3$ is similar to a strongly regular graph, have $k = O(v^{1 - \frac{1}{3m-2i-5}})$ .

preprint2022arXiv

Non-Geometric Cospectral Mates of Line Graphs with a Linear Representation

For an incidence geometry $\mathcal{G} = (\mathcal{P}, \mathcal{L}, \text{I})$ with a linear representation $\mathcal{T}_n^*(\mathcal{K})$ , we apply WQH switching to construct a non-geometric graph $Γ'$ cospectral with the line graph $Γ$ of $\mathcal{G}$ . As an application, we show that for $h \geq 2$ and $0 < m < h$ , there are strongly regular graphs with parameters $(v, k, λ, μ) = (2^{2h} (2^{m+h}+2^m-2^h), 2^h (2^h+1)(2^m-1), 2^h (2^{m+1}-3), 2^h (2^m-1))$ which are not point graphs of partial geometries of order $(s,t,α) = ((2^h+1)(2^m-1), 2^h-1, 2^m-1)$ .

preprint2022arXiv

Switching for Small Strongly Regular Graphs

We provide an abundance of strongly regular graphs (SRGs) for certain parameters $(n, k, λ, μ)$ with $n < 100$ . For this we use Godsil-McKay (GM) switching with a partition of type $4,n-4$ and Wang-Qiu-Hu (WQH) switching with a partition of type $3,3,n-6$ or $4,4,n-8$ . In most cases, we start with a highly symmetric graph which belongs to a finite geometry. Many of the obtained graphs are new; for instance, we find 16565438 strongly regular graphs with parameters $(81, 30, 9, 12)$ while only 15 seem to be described in the literature. We provide statistics about the size of the occurring automorphism groups. We also find the recently discovered Krčadinac partial geometry, thus finding a third method of constructing it.

preprint2022arXiv

The least Euclidean distortion constant of a distance-regular graph

In 2008, Vallentin made a conjecture involving the least distortion of an embedding of a distance-regular graph into Euclidean space. Vallentin's conjecture implies that for a least distortion Euclidean embedding of a distance-regular graph of diameter $d$ , the most contracted pairs of vertices are those at distance $d$ . In this paper, we confirm Vallentin's conjecture for several families of distance-regular graphs. We also provide counterexamples to this conjecture, where the largest contraction occurs between pairs of vertices at distance $d{-}1$ . We suggest three alternative conjectures and prove them for several families of distance-regular graphs.

preprint2021arXiv

Cameron-Liebler $k$ -sets in $\text{AG}(n,q)$

We study Cameron-Liebler $k$ -sets in the affine geometry, so sets of $k$ -spaces in $\text{AG}(n, q)$ . This generalizes research on Cameron-Liebler $k$ -sets in the projective geometry $\text{PG}(n, q)$ . Note that in algebraic combinatorics, Cameron-Liebler $k$ -sets of $\text{AG}(n, q)$ correspond to certain equitable bipartitions of the Association scheme of $k$ -spaces in $\text{AG}(n, q)$ , while in the analysis of Boolean functions, they correspond to Boolean degree $1$ functions of $\text{AG}(n, q)$ . We define Cameron-Liebler $k$ -sets in $\text{AG}(n, q)$ by intersection properties with $k$ -spreads and show the equivalence of several definitions. In particular, we investigate the relationship between Cameron-Liebler $k$ -sets in $\text{AG}(n, q)$ and $\text{PG}(n, q)$ . As a by-product, we calculate the character table of the association scheme of affine lines. Furthermore, we characterize the smallest examples of Cameron-Liebler $k$ -sets. This paper focuses on $\text{AG}(n, q)$ for $n > 3$ , while the case for Cameron-Liebler line classes in $\text{AG}(3, q)$ was already treated separately.

preprint2021arXiv

Ovoids of Generalized Quadrangles of Order $(q, q^2-q)$ and Delsarte Cocliques in Related Strongly Regular Graphs

We investigate strongly regular graphs for which Hoffman's ratio bound and Cvetcović's inertia bound are equal. This means that $ve^- = m^-(e^- - k)$ , where $v$ is the number of vertices, $k$ is the regularity, $e^-$ is the smallest eigenvalue, and $m^-$ is the multiplicity of $e^-$ . We show that Delsarte cocliques do not exist for all Taylor's $2$ -graphs and for point graphs of generalized quadrangles of order $(q,q^2-q)$ for infinitely many $q$ . For cases where equality may hold, we show that for nearly all parameter sets, there are at most two Delsarte cocliques.

preprint2020arXiv

A construction for clique-free pseudorandom graphs

A construction of Alon and Krivelevich gives highly pseudorandom $K_k$ -free graphs on $n$ vertices with edge density equal to $Θ(n^{-1/(k -2)})$ . In this short note we improve their result by constructing an infinite family of highly pseudorandom $K_k$ -free graphs with a higher edge density of $Θ(n^{-1/(k - 1)})$ .

preprint2020arXiv

A Note on a Construction by Pavese and Smaldore

Recently, Pavese and Smaldore constructed graphs cospectral to $NU(5, q^2)$ for $q>2$ . We show that their construction works for $NU(n, q^2)$ , $n \geq 5$ . Hence, none of the graphs $NU(n, q^2)$ , $n \geq 5$ , are determined by their spectrum.

preprint2020arXiv

New Bounds for Partial Spreads of $H(2d-1, q^2)$ and Partial Ovoids of the Ree-Tits Octagon

Two results are obtained that give upper bounds on partial spreads and partial ovoids respectively. The first result is that the size of a partial spread of the Hermitian polar space $\mathsf{H}(3, q^2)$ is at most $\left(\frac{2p^3+p}{3} \right)^t+1$ , where $q=p^t$ , $p$ is a prime. For fixed $p$ this bound is in $o(q^3)$ , which is asymptotically better than the previous best known bound of $(q^3+q+2)/2$ . Similar bounds for partial spreads of $\mathsf{H}(2d-1, q^2)$ , $d$ even, are given. The second result is that the size of a partial ovoid of the Ree-Tits octagon $\mathsf{O}(2^t)$ is at most $26^t+1$ . This bound, in particular, shows that the Ree-Tits octagon $\mathsf{O}(2^t)$ does not have an ovoid.

preprint2020arXiv

New bounds on the Ramsey number $r(I_m, L_n)$

We investigate the Ramsey numbers $r(I_m, L_n)$ which is the minimal natural number $k$ such that every oriented graph on $k$ vertices contains either an independent set of size $m$ or a transitive tournament on $n$ vertices. Apart from the finitary combinatorial interest, these Ramsey numbers are of interest to set theorists since it is known that $r(ωm, n) = ωr(I_m, L_n)$ , where $ω$ is the lowest transfinite ordinal number, and $r(κm, n) = κr(I_m, L_n)$ for all initial ordinals $κ$ . Continuing the research by Bermond from 1974 who did show $r(I_3, L_3) = 9$ , we prove $r(I_4, L_3) = 15$ and $r(I_5, L_3) = 23$ . The upper bounds for both the estimates above are obtained by improving the upper bound of $m^2$ on $r(I_m, L_3)$ due to Larson and Mitchell (1997) to $m^2 - m + 3$ . Additionally, we provide asymptotic upper bounds on $r(I_m, L_n)$ for all $n \geq 3$ . In particular, we show that $r(I_m, L_3) \in Θ(m^2 / \log m)$ .

preprint2020arXiv

Remarks on the Erdős Matching Conjecture for Vector Spaces

In 1965, Paul Erdős asked about the largest family $Y$ of $k$ -sets in $\{ 1, \ldots, n \}$ such that $Y$ does not contain $s+1$ pairwise disjoint sets. This problem is commonly known as the Erdős Matching Conjecture. We investigate the $q$ -analog of this question, that is we want to determine the size of a largest family $Y$ of $k$ -spaces in $\mathbb{F}_q^n$ such that $Y$ does not contain $s+1$ pairwise disjoint $k$ -spaces. Here we call two subspaces disjoint if they intersect trivially. Our main result is, slightly simplified, that if $16 s \leq \min\{ q^{\frac{n-k}{4}},$ $q^{\frac{n-2k+1}{3}} \}$ , then $Y$ is either small or a union of intersecting families. Thus we show the Erd\H{os} Matching Conjecture for this range. The proof uses a method due to Metsch. We also discuss constructions. In particular, we show that for larger $s$ , there are large examples which are close in size to a union of intersecting families, but structurally different. As an application, we discuss the close relationship between the Erdős Matching Conjecture for vector spaces and Cameron-Liebler line classes (and their generalization to $k$ -spaces), a popular topic in finite geometry for the last 30 years. More specifically, we propose the Erdős Matching Conjecture (for vector spaces) as an interesting variation of the classical research on Cameron-Liebler line classes.

preprint2020arXiv

The Chromatic Number of the $q$ -Kneser Graph for $q \geq 5$

We obtain a new weak Hilton-Milner type result for intersecting families of $k$ -spaces in $\mathbb{F}_q^{2k}$ , which improves several known results. In particular the chromatic number of the $q$ -Kneser graph $qK_{n:k}$ was previously known for $n > 2k$ (except for $n=2k+1$ and $q=2$ ) or $k < q \log q - q$ . Our result determines the chromatic number of $qK_{2k:k}$ for $q \geq 5$ , so that the only remaining open cases are $(n, k) = (2k, k)$ with $q \in \{ 2, 3, 4 \}$ and $(n, k) = (2k+1, k)$ with $q = 2$ .

preprint2016arXiv

Infection in Hypergraphs

In this paper a new parameter for hypergraphs called hypergraph infection is defined. This concept generalizes zero forcing in graphs to hypergraphs. The exact value of the infection number of complete and complete bipartite hypergraphs is determined. A formula for the infection number for interval hypergraphs and several families of cyclic hypergraphs is given. The value of the infection number for a hypergraph whose edges form a symmetric t-design is given, and bounds are determined for a hypergraph whose edges are a t-design. Finally, the infection number for several hypergraph products and line graphs are considered.

preprint2016arXiv

Some non-existence results for distance- $j$ ovoids in small generalized polygons

We give a computer-based proof for the non-existence of distance- $2$ ovoids in the dual split Cayley hexagon $\mathsf{H}(4)^D$ . Furthermore, we give upper bounds on partial distance- $2$ ovoids of $\mathsf{H}(q)^D$ for $q \in \{2, 4\}$ .

preprint2015arXiv

A Note on the Manickam-Miklós-Singhi Conjecture for Vector Spaces

Let $V$ be an $n$ -dimensional vector space over a finite field $\mathbb{F}_q$ . Define a real-valued weight function on the $1$ -dimensional vector spaces of $V$ such that the sum of all weights is zero. Let the weight of a subspace $S$ be the sum of the weights of the $1$ -dimensional subspaces contained in $S$ . In 1988 Manickam and Singhi conjectured that if $n \geq 4k$ , then the number of $k$ -dimensional subspaces with nonnegative weight is at least the number of $k$ -dimensional subspaces on a fixed $1$ -dimensional subspace. Recently, Chowdhury, Huang, Sarkis, Shahriari, and Sudakov proved the conjecture of Manickam and Singhi for $n \geq 3k$ . We modify the technique used by Chowdhury et al. to prove the conjecture for $n \geq 2k$ if $q$ is large. Furthermore, if equality holds and $n \geq 2k+1$ , then the set of $k$ -dimensional subspaces with nonnegative weight is the set of all $k$ -dimensional subspaces on a fixed $1$ -dimensional subspace.

preprint2015arXiv

Large $\{0, 1, \ldots, t\}$ -Cliques in Dual Polar Graphs

We investigate $\{0, 1, \ldots, t \}$ -cliques of generators on dual polar graphs of finite classical polar spaces of rank $d$ . These cliques are also known as Erdős-Ko-Rado sets in polar spaces of generators with pairwise intersections in at most codimension $t$ . Our main result is that we classify all such cliques of maximum size for $t \leq \sqrt{8d/5}-2$ if $q \geq 3$ , and $t \leq \sqrt{8d/9}-2$ if $q = 2$ . We have the following byproducts. (a) For $q \geq 3$ we provide estimates of Hoffman's bound on these $\{0, 1, \ldots, t \}$ -cliques for all $t$ . (b) For $q \geq 3$ we determine the largest, second largest, and smallest eigenvalue of the graphs which have the generators of a polar space as vertices and where two generators are adjacent if and only if they meet in codimension at least $t+1$ . Furthermore, we provide nice explicit formulas for all eigenvalues of these graphs. (c) We provide upper bounds on the size of the second largest maximal $\{0, 1, \ldots, t \}$ -cliques for some $t$ .

preprint2015arXiv

Weighted Intriguing Sets in Finite Polar Spaces

We provide new proofs for the non-existence of ovoids in hyperbolic spaces of rank at least four in even characteristic, and for the Hermitian polar space $\mathsf{H}(5, 4)$ . We also improve the results of A. Klein on the non-existence of ovoids of Hermitian spaces and hyperbolic quadrics.

preprint2014arXiv

A Characterization of the Natural Embedding of the Split Cayley Hexagon in PG(6,q) by Intersection Numbers in Finite Projective Spaces of Arbitrary Dimension

We prove that a non-empty set L of at most q^5+q^4+q^3+q^2+q+1 lines of PG(n, q) with the properties that (1) every point of PG(n,q) is incident with either 0 or q+1 elements of L, (2) every plane plane of PG(n, q) is incident with either 0, 1 or q+1 elements of L, (3) every solid of PG(n, q) is incident with either 0, 1, q+1 or 2q+1 elements of L, and (4) every 4-dimensional subspace of PG(n, q) is incident with at most q^3-q^2+4q elements of L, is necessarily the set of lines of a split Cayley hexagon H(q) naturally embedded in PG(6, q).

preprint2014arXiv

Cross-Intersecting Erdős-Ko-Rado Sets in Finite Classical Polar Spaces

A cross-intersecting Erdős-Ko-Rado set of generators of a finite classical polar space is a pair $(Y, Z)$ of sets of generators such that all $y \in Y$ and $z \in Z$ intersect in at least a point. We provide upper bounds on $|Y| \cdot |Z|$ and classify the cross-intersecting Erdős-Ko-Rado sets of maximum size with respect to $|Y| \cdot |Z|$ for all polar spaces except Hermitian polar spaces in odd projective dimension.

Ferdinand Ihringer

Research overview

Is this your work?

19 publications

Approximately Strongly Regular Graphs

Non-Geometric Cospectral Mates of Line Graphs with a Linear Representation

Switching for Small Strongly Regular Graphs

The least Euclidean distortion constant of a distance-regular graph

Cameron-Liebler $k$ -sets in $\text{AG}(n,q)$

Ovoids of Generalized Quadrangles of Order $(q, q^2-q)$ and Delsarte Cocliques in Related Strongly Regular Graphs

A construction for clique-free pseudorandom graphs

A Note on a Construction by Pavese and Smaldore

New Bounds for Partial Spreads of $H(2d-1, q^2)$ and Partial Ovoids of the Ree-Tits Octagon

New bounds on the Ramsey number $r(I_m, L_n)$

Remarks on the Erdős Matching Conjecture for Vector Spaces

The Chromatic Number of the $q$ -Kneser Graph for $q \geq 5$

Infection in Hypergraphs

Some non-existence results for distance- $j$ ovoids in small generalized polygons

A Note on the Manickam-Miklós-Singhi Conjecture for Vector Spaces

Large $\{0, 1, \ldots, t\}$ -Cliques in Dual Polar Graphs

Weighted Intriguing Sets in Finite Polar Spaces

A Characterization of the Natural Embedding of the Split Cayley Hexagon in PG(6,q) by Intersection Numbers in Finite Projective Spaces of Arbitrary Dimension

Cross-Intersecting Erdős-Ko-Rado Sets in Finite Classical Polar Spaces

See the researcher in context

Building this map preview

Ferdinand Ihringer

Research overview

Is this your work?

19 publications

Approximately Strongly Regular Graphs

Non-Geometric Cospectral Mates of Line Graphs with a Linear Representation

Switching for Small Strongly Regular Graphs

The least Euclidean distortion constant of a distance-regular graph

Cameron-Liebler kkk-sets in AG(n,q)\text{AG}(n,q)AG(n,q)

Ovoids of Generalized Quadrangles of Order (q,q2−q)(q, q^2-q)(q,q2−q) and Delsarte Cocliques in Related Strongly Regular Graphs

A construction for clique-free pseudorandom graphs

A Note on a Construction by Pavese and Smaldore

New Bounds for Partial Spreads of H(2d−1,q2)H(2d-1, q^2)H(2d−1,q2) and Partial Ovoids of the Ree-Tits Octagon

New bounds on the Ramsey number r(Im,Ln)r(I_m, L_n)r(Im​,Ln​)

Remarks on the Erdős Matching Conjecture for Vector Spaces

The Chromatic Number of the qqq-Kneser Graph for q≥5q \geq 5q≥5

Infection in Hypergraphs

Some non-existence results for distance-jjj ovoids in small generalized polygons

A Note on the Manickam-Miklós-Singhi Conjecture for Vector Spaces

Large {0,1,…,t}\{0, 1, \ldots, t\}{0,1,…,t}-Cliques in Dual Polar Graphs

Weighted Intriguing Sets in Finite Polar Spaces

A Characterization of the Natural Embedding of the Split Cayley Hexagon in PG(6,q) by Intersection Numbers in Finite Projective Spaces of Arbitrary Dimension

Cross-Intersecting Erdős-Ko-Rado Sets in Finite Classical Polar Spaces

See the researcher in context

Building this map preview

Cameron-Liebler $k$ -sets in $\text{AG}(n,q)$

Ovoids of Generalized Quadrangles of Order $(q, q^2-q)$ and Delsarte Cocliques in Related Strongly Regular Graphs

New Bounds for Partial Spreads of $H(2d-1, q^2)$ and Partial Ovoids of the Ree-Tits Octagon

New bounds on the Ramsey number $r(I_m, L_n)$

The Chromatic Number of the $q$ -Kneser Graph for $q \geq 5$

Some non-existence results for distance- $j$ ovoids in small generalized polygons

Large $\{0, 1, \ldots, t\}$ -Cliques in Dual Polar Graphs