Search

A storage code on a graph G is a set of assignments of symbols to the vertices such that every vertex can recover its value by looking at its neighbors. We consider the question of constructing large-size storage codes on triangle-free graphs constructed as coset graphs of binary linear codes. Previously it was shown that there are infinite families of binary storage codes on coset graphs with rate converging to 3/4. Here we show that codes on such graphs can attain rate asymptotically approaching 1. Equivalently, this question can be phrased as a version of hat-guessing games on graphs (e.g., Cameron et al., in: Electron J Combin 23(1):48, 2016). In this language, we construct triangle-free graphs with success probability of the players approaching one as the number of vertices tends to infinity. Furthermore, finding linear index codes of rate approaching zero is also an equivalent problem. [ABSTRACT FROM AUTHOR]

In this paper we prove that every totally real algebraic integer λ of degree d ≥ 2 occurs as an eigenvalue of some tree of height at most d (d + 1) / 2 + 3 . In order to prove this, for a given algebraic number α ≠ 0 , we investigate an additive semigroup that contains zero and is closed under the map x ↦ α / (1 - x) for x ≠ 1 . The problem of finding the smallest such semigroup seems to be of independent interest. [ABSTRACT FROM AUTHOR]

The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest in this question dates back to the early 1980 s, when P. J. Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by Babai (J Graph Theory 9:363–370, 1985). Then Babai posed the open problems of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this paper, we solve Babai's problems by constructing an infinite family of s-arc-transitive digraphs for each integer s ≥ 2 , and an infinite family of vertex-primitive digraphs, both of whose adjacency matrices are non-diagonalizable. [ABSTRACT FROM AUTHOR]

Given q-uniform hypergraphs (q-graphs) F, G and H, where G is a spanning subgraph of F, G is called weaklyH-saturated in F if the edges in E (F) \ E (G) admit an ordering e 1 , ... , e k so that for all i ∈ [ k ] the hypergraph G ∪ { e 1 , ... , e i } contains an isomorphic copy of H which in turn contains the edge e i . The weak saturation number of H in F is the smallest size of an H-weakly saturated subgraph of F. Weak saturation was introduced by Bollobás in 1968, but despite decades of study our understanding of it is still limited. The main difficulty lies in proving lower bounds on weak saturation numbers, which typically withstands combinatorial methods and requires arguments of algebraic or geometrical nature. In our main contribution in this paper we determine exactly the weak saturation number of complete multipartite q-graphs in the directed setting, for any choice of parameters. This generalizes a theorem of Alon from 1985. Our proof combines the exterior algebra approach from the works of Kalai with the use of the colorful exterior algebra motivated by the recent work of Bulavka, Goodarzi and Tancer on the colorful fractional Helly theorem. In our second contribution answering a question of Kronenberg, Martins and Morrison, we establish a link between weak saturation numbers of bipartite graphs in the clique versus in a complete bipartite host graph. In a similar fashion we asymptotically determine the weak saturation number of any complete q-partite q-graph in the clique, generalizing another result of Kronenberg et al. [ABSTRACT FROM AUTHOR]

We study the problem of determining the maximum size of a spherical two-distance set with two fixed angles (one acute and one obtuse) in high dimensions. Let N α , β (d) denote the maximum number of unit vectors in R d where all pairwise inner products lie in { α , β } . For fixed - 1 ≤ β < 0 ≤ α < 1 , we propose a conjecture for the limit of N α , β (d) / d as d → ∞ in terms of eigenvalue multiplicities of signed graphs. We determine this limit when α + 2 β < 0 or (1 - α) / (α - β) ∈ { 1 , 2 , 3 } . Our work builds on our recent resolution of the problem in the case of α = - β (corresponding to equiangular lines). It is the first determination of lim d → ∞ N α , β (d) / d for any nontrivial fixed values of α and β outside of the equiangular lines setting. [ABSTRACT FROM AUTHOR]

We work out the theory of fractional isomorphism of graphons as a generalization to the classical theory of fractional isomorphism of finite graphs. The generalization is given in terms of homomorphism densities of finite trees and it is characterized in terms of distributions on iterated degree measures, Markov operators, weak isomorphism of a conditional expectation with respect to invariant sub-σ-algebras and isomorphism of certain quotients of given graphons. [ABSTRACT FROM AUTHOR]

An (n, d, λ)-graph is a d regular graph on n vertices in which the absolute value of any nontrivial eigenvalue is at most λ. For any constant d ≥ 3, ϵ > 0 and all sufficiently large n we show that there is a deterministic poly(n) time algorithm that outputs an (n, d, λ)-graph (on exactly n vertices) with λ ≤ 2 d − 1 + ϵ . For any d=p + 2 with p ≡ 1 mod 4 prime and all sufficiently large n, we describe a strongly explicit construction of an (n, d, λ)-graph (on exactly n vertices) with λ ≤ 2 (d − 1) + d − 2 + o (1) (< (1 + 2) d − 1 + o (1)) , with the o(1) term tending to 0 as n tends to infinity. For every ϵ> 0, d> d0(ϵ) and n>n0(d, ϵ) we present a strongly explicit construction of an (m, d, λ)-graph with λ < (2 + ϵ) d and m = n + o(n). All constructions are obtained by starting with known Ramanujan or nearly Ramanujan graphs and modifying or packing them in an appropriate way. The spectral analysis relies on the delocalization of eigenvectors of regular graphs in cycle-free neighborhoods. [ABSTRACT FROM AUTHOR]

In his PhD thesis Shih characterized the relationship between two graphs, where the cycle space of the first is included in the cycle space of the second and the dimension of the cycle spaces differ by one [7]. However, this result never appeared in a refereed publication. As a consequence this theorem has not received the attention it deserves. We give a simpler and shorter proof of this result as well as several restatements that are of independent interest. In addition, we mention applications to even-cycle matroids, even-cut matroids and frame matroids. [ABSTRACT FROM AUTHOR]

Let A be a random m × n matrix over the finite field F q with precisely k non-zero entries per row and let y ∈ F q m be a random vector chosen independently of A. We identify the threshold m/n up to which the linear system Ax = y has a solution with high probability and analyse the geometry of the set of solutions. In the special case q = 2, known as the random k-XORSAT problem, the threshold was determined by [Dubois and Mandler 2002 for k = 3, Pittel and Sorkin 2016 for k > 3], and the proof technique was subsequently extended to the cases q = 3,4 [Falke and Goerdt 2012]. But the argument depends on technically demanding second moment calculations that do not generalise to q > 4. Here we approach the problem from the viewpoint of a decoding task, which leads to a transparent combinatorial proof. [ABSTRACT FROM AUTHOR]

The bilinear forms graph denoted here by Bilq(d×e) is a graph defined on the set of (d×e)-matrices (e≥d) over F q with two matrices being adjacent if and only if the rank of their difference equals 1. In 1999, K. Metsch showed that the bilinear forms graph Bilq(d×e), d≥3, is characterized by its intersection array if one of the following holds: — q=2 and e≥d+4 — q≥3 and e≥d+3. Thus, the following cases have been left unsettled: — q=2 and e∈{d,d+1,d+2,d+3} — q≥3 and e∈{d,d+1,d+2}. In this work, we show that the graph of bilinear (d×d)-forms over the binary field, where d≥3, is characterized by its intersection array. In doing so, we also classify locally grid graphs whose μ-graphs are hexagons and their intersection numbers bi,ci are well-defined for all i=0,1,2. [ABSTRACT FROM AUTHOR]

Let G be a bipartite graph with adjacency matrix A. If G has a unique perfect matching, then A has an inverse A1 which is a symmetric integral matrix, and hence the adjacency matrix of a multigraph. The inverses of bipartite graphs with unique perfect matchings have a strong connection to Möbius functions of posets. In this note, we characterize all bipartite graphs with a unique perfect matching whose adjacency matrices have inverses diagonally similar to non-negative matrices, which settles an open problem of Godsil on inverses of bipartite graphs in [Godsil, Inverses of Trees, Combinatorica 5 (1985) 33-39]. [ABSTRACT FROM AUTHOR]

Let M =( ξ ) be a real symmetric random matrix in which the upper-triangular entries ξ , i < j and diagonal entries ξ are independent. We show that with probability tending to 1, M has no repeated eigenvalues. As a corollary, we deduce that the Erdős-Rényi random graph has simple spectrum asymptotically almost surely, answering a question of Babai. [ABSTRACT FROM AUTHOR]

We investigate vector chromatic number ( χ ), Lovász V-function of the complement $$(\bar \vartheta )$$ , and quantum chromatic number ( χ ) from the perspective of graph homomorphisms. We prove an analog of Sabidussi's theorem for each of these parameters, i.e., that for each of the parameters, the value on the Cartesian product of graphs is equal to the maximum of the values on the factors. Interestingly, as a consequence of this result for $$\bar \vartheta$$ , we obtain analog of Hedetniemi's conjecture, i.e., that the value of $$\bar \vartheta$$ on the categorical product of graphs is equal to the minimum of its values on the factors. We conjecture that the analogous results hold for vector and quantum chromatic number, and we prove that this is the case for some special classes of graphs. [ABSTRACT FROM AUTHOR]

A total weighting of a graph G is a mapping ϕ that assigns to each element z ∈ V ( G)∪ E( G) a weight ϕ( z). A total weighting ϕ is proper if for any two adjacent vertices u and v, ∑ ϕ( e)+ ϕ( u)≠∑ ϕ( e)+ ϕ( v). This paper proves that if each edge e is given a set L( e) of 3 permissible weights, and each vertex v is given a set L( v) of 2 permissible weights, then G has a proper total weighting ϕ with ϕ( z) ∈ L( z) for each element z ∈ V ( G)∪ E( G). [ABSTRACT FROM AUTHOR]

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. Akbari, Cameron, and Khosrovshahi conjectured that the number of vertices of every reduced graph of rank r is at most m( r)=2−2 if r is even and m( r)=5·2−2 if r is odd. In this article, we prove that if the conjecture is not true, then there would be a counterexample of rank at most 46. We also show that every reduced graph of rank r has at most 8 m( r)+14 vertices. [ABSTRACT FROM AUTHOR]

Explicit construction of Ramsey graphs or graphs with no large clique or independent set, has remained a challenging open problem for a long time. While Erdös' probabilistic argument shows the existence of graphs on 2n vertices with no clique or independent set of size 2, the best explicit constructions achieve a far weaker bound. There is a connection between Ramsey graph constructions and polynomial representations of Boolean functions due to Grolmusz; a low degree representation for the OR function can be used to explicitly construct Ramsey graphs [17,18]. We generalize the above relation by proposing a new framework. We propose a new definition of OR representations: a pair of polynomials represent the OR function if the union of their zero sets contains all points in {0, 1} except the origin. We give a simple construction of a Ramsey graph using such polynomials. Furthermore, we show that all the known algebraic constructions, ones to due to Frankl-Wilson [12], Grolmusz [18] and Alon [2] are captured by this framework; they can all be derived from various OR representations of degree O(√ n) based on symmetric polynomials. Thus the barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations. Using new algebraic techniques, we show that better bounds cannot be obtained using symmetric polynomials. [ABSTRACT FROM AUTHOR]

Let F be a family of graphs. A graph is F-free if it contains no copy of a graph in F as a subgraph. A cornerstone of extremal graph theory is the study of the Turán number ex( n,F), the maximum number of edges in an F-free graph on n vertices. Define the Zarankiewicz number z( n,F) to be the maximum number of edges in an F-free bipartite graph on n vertices. Let C denote a cycle of length k, and let C denote the set of cycles C, where 3≤ℓ≤ k and ℓ and k have the same parity. Erdős and Simonovits conjectured that for any family F consisting of bipartite graphs there exists an odd integer k such that ex( n,F ∪ C) ∼ z( n,F) - here we write f(n) ∼ g(n) for functions f,g: ℕ → ℝ if lim f(n)/g(n)=1. They proved this when F ={ C} by showing that ex( n,{ C; C})∼z( n,C). In this paper, we extend this result by showing that if ℓ∈{2,3,5} and k>2ℓ is odd, then ex( n,C∪{ C}) ∼ z( n, C). Furthermore, if k>2ℓ+2 is odd, then for infinitely many n we show that the extremal C∪{ C}-free graphs are bipartite incidence graphs of generalized polygons. We observe that this exact result does not hold for any odd k<2ℓ, and furthermore the asymptotic result does not hold when ( ℓ,k) is (3, 3), (5, 3) or (5, 5). Our proofs make use of pseudorandomness properties of nearly extremal graphs that are of independent interest. [ABSTRACT FROM AUTHOR]

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2 n vertices, with a covering map π : H → G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range $$ {\left[ { - 2{\sqrt {d - 1} },2{\sqrt {d - 1} }} \right]} $$ (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range $$ {\left[ { - c{\sqrt {d\log ^{3} d} },c{\sqrt {d\log ^{3} d} }} \right]} $$ for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue $$ O{\left( {{\sqrt {d\log ^{3} d} }} \right)} $$. The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l1 norm of each row in A is at most d. Suppose that $$ \frac{{{\left| {x^{t} Ay} \right|}}} {{{\left\| x \right\|}{\left\| y \right\|}}} \leqslant \alpha $$ for every x,y ∈{0,1} n with ‹ x,y›=0. Then the spectral radius of A is O(α(log( d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. [ABSTRACT FROM AUTHOR]

Given a graph G on n nodes, let denote the cone consisting of the positive semidefinite matrices (with real or complex entries) having a zero entry at every off-diagonal position corresponding to a non edge of G. Then, the sparsity order of G is defined as the maximum rank of a matrix lying on an extreme ray of the cone . It is known that the graphs with sparsity order 1 are the chordal graphs and a characterization of the graphs with sparsity order 2 is conjectured in [1] in the real case. We show in this paper the validity of this conjecture. Moreover, we characterize the graphs with sparsity order 2 in the complex case and we give a decomposition result for the graphs with sparsity order in both real and complex cases. As an application, these graphs can be recognized in polynomial time. We also indicate how an inequality from [17] relating the sparsity order of a graph and its minimum fill-in can be derived from a result concerning the dimension of the faces of the cone . [ABSTRACT FROM AUTHOR]

, we denote by its smallest non-zero Laplacian eigenvalue. In this paper we show that among all sets of n-1 transpositions which generate the symmetric group, , the set whose associated Cayley graph has the highest is the set {(1, n), (2, n), ..., ( n-1, n)} (or the same with n and i exchanged for any i< n). For this set we have . This result follows easily from the following result. For any set of transpositions, T, we can form a graph on n vertices, , by forming an edge {i, j} in for each transposition . We prove that if is bipartite, then of the Cayley graph associated to T is at most ; left open is the compelling conjecture that the two 's are always equal. We discuss this and other generalizations of Bacher's work, which dealt with the case T = {(1, 2), (2, 3), ..., ( n-1, n)}. [ABSTRACT FROM AUTHOR]

. This approach refines results relating the spectral gap of a graph to the so-called magnification of a graph. A concentration result involving is also derived. [ABSTRACT FROM AUTHOR]

if every principal submatrix has determinant 0 or ±1. Let A be a symmetric (0, 1)-matrix, with a zero diagonal. A PU-orientation of A is a skew-symmetric signing of A that is PU. If A′ is a PU-orientation of A, then, by a certain decomposition of A, we can construct every PU-orientation of A from A′. This construction is based on the fact that the PU-orientations of indecomposable matrices are unique up to negation and multiplication of certain rows and corresponding columns by −1. This generalizes the well-known result of Camion, that if a (0, 1)-matrix can be signed to be totally unimodular then the signing is unique up to multiplying certain rows and columns by −1. Camion's result is an easy but crucial step in proving Tutte's famous excluded minor characterization of totally unimodular matrices. [ABSTRACT FROM AUTHOR]

This paper concerns the open problem of Lovász and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems. [ABSTRACT FROM AUTHOR]

By introducing a duality operator in coherent algebras (i.e. adjacency algebras of coherent configurations) we give a new interpretation to Delsarte's duality theory for association schemes. In particular we show that nonnegative matrices and positive semidefinite matrices, (0, 1)-matrices and distance matrices, regular graphs and spherical 2-designs, distance regular graphs and Delsarte matricesare pairs of dual objects. Several 'almost dual' properties which are not yet fully understood are also reported. [ABSTRACT FROM AUTHOR]

Let $$ \Lambda ^{k}_{n} $$ denote the set of n× n binary matrices which have each row and column sum equal to k. For 2≤ k≤ n→∞ we show that $$ {\left( {\min _{{A \in \Lambda ^{k}_{n} }} {\text{per}}{\kern 1pt} A} \right)}^{{1/n}} $$ is asymptotically equal to ( k−1) k−1 k2− k. This confirms Conjecture 23 in Minc's catalogue of open problems. [ABSTRACT FROM AUTHOR]