A Contribution to the Second Neighborhood Problem

Seymour’s Second Neighborhood Conjecture asserts that every oriented graph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. It is proved for tournaments, tournaments missing a matching and tournaments missing a generalized star. We prove this conjecture for classes of oriented graphs whose missing graph is a comb, a complete graph minus two independent edges, or a cycle of length 5.     

The Arc‐Weighted Version of the Second Neighborhood Conjecture

Seymour conjectured that every oriented simple graph contains a vertex whose second neighborhood is at least as large as its first. Seymour's conjecture has been verified in several special cases, most notably for tournaments by Fisher  6 . One extension of the conjecture that has been used by several researchers is to consider vertex‐weighted digraphs. In this article we introduce a version of the conjecture for arc‐weighted digraphs. We prove the conjecture in the special case of arc‐weighted tournaments, strengthening Fisher's theorem. Our proof does not rely on Fisher's result, and thus can be seen as an alternate proof of said theorem.     

The union-closed sets conjecture almost holds for almost all random bipartite graphs

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.     

Proof of the squashed cube conjecture

We prove a conjecture of R. L. Graham and H. O. Pollak to the effect that every connected graph onn vertices has a distance-preserving embedding in “squashed cube” of dimensionn?1. This means that to each vertex of the graph a string ofn?1 symbols from the alphabet {0, 1, *} can be assigned in such a way that the length of the shortest path between two vertices is equal to the Hamming distance between the corresponding strings, with * being regarded as at distance zero from either 1 or 0. Our labelling thus provides an efficient addressing scheme for the loop-switching communications system proposed by J. R. Pierce.     

20 Years of Negami’s Planar Cover Conjecture

In 1988, Seiya Negami published a conjecture stating that a graph G has a finite planar cover (i.e. a homomorphism from some planar graph onto G which maps the vertex neighbourhoods bijectively) if and only if G embeds in the projective plane. Though the “if” direction is easy, and over ten related research papers have been published during the past 20 years of investigation, this beautiful conjecture is still open in 2008. We give a short accessible survey on Negami’s conjecture and all the (so far) published partial results, and outline some further ideas to stimulate future research towards solving the conjecture.     

Multiple cover time

Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distribution. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the following conjecture: that the blanket time of a graph never exceeds the cover time by more than a constant factor. In other words, at the cost of a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case includes almost all graphs, as well as most “natural” graphs: the hypercube, k-dimensional lattices for k ≥ 2, balanced k-ary trees, and expanders. We further prove the conjecture for perhaps the most natural graphs not falling in the above case: paths and cycles. Finally, we prove the conjecture in the case of independent stochastic processes. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 403–411 (1996)     

Connectivity threshold of Bluetooth graphs

We study the connectivity properties of random Bluetooth graphs that model certain “ad hoc” wireless networks. The graphs are obtained as “irrigation subgraphs” of the well‐known random geometric graph model. There are two parameters that control the model: the radius r that determines the “visible neighbors” of each vertex and the number of edges c that each vertex is allowed to send to these. The randomness comes from the underlying distribution of vertices in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters r, c and completely characterize the connectivity threshold (in c) for values of r close the critical value for connectivity in the underlying random geometric graph.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 45–66, 2014     

Remarks on the second neighborhood problem

The second neighborhood conjecture of Seymour asserts that for any orientation G = (V,E), there exists a vertex υ ∈ V so that |N⁺(υ)| ≤ |N⁺⁺(υ)|. The conjecture was resolved by Fisher for tournaments. In this article, we prove the second neighborhood conjecture for several additional classes of dense orientations. We also prove some approximation results, and reduce an asymptotic version of the conjecture to a finite case. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 208–220, 2007     

Estimates of eigenvalues of the Laplacian by a reduced number of subsets

Chung–Grigor’yan–Yau’s inequality describes upper bounds of eigenvalues of the Laplacian in terms of subsets (“input”) and their volumes. In this paper we will show that we can reduce “input” in Chung–Grigor’yan–Yau’s inequality in the setting of Alexandrov spaces satisfying CD(0,∞). We will also discuss a related conjecture for some universal inequality among eigenvalues of the Laplacian.     

On Turán’s (3,4)-problem with forbidden subgraphs

We identify three 3-graphs on five vertices that are missing in all known extremal configurations for Turán’s (3,4)-problem and prove Turán’s conjecture for 3-graphs that are additionally known not to contain any induced copies of these 3-graphs. Our argument is based on an (apparently) new technique of “indirect interpretation” that allows us to retrieve additional structure from hypothetical counterexamples to Turán’s conjecture, but in rather loose and limited sense. We also include two miscellaneous calculations in flag algebras that prove similar results about some other additional forbidden subgraphs.     

Empirical study of stochasticity for deterministic chaotical dynamics of geometric progressions of residues

Kolmogorov discovered in 1933 that the empirical statistics of several independent values of any random variable differs from the true distribution function of this variable in some universal way: the random distribution of the distance of one of these statistics from the other verifies (asymptotically) some stochastic distribution law (called later “Kolmogorov’s distribution”). The present paper compares the Kolmogorov’s distribution with a similar object, provided by the chain of observations of a nonrandom, deterministic dynamical system, formed by the consecutive members of a geometrical progression. Say, the Kolmogorov’s distribution is observed for the distribution of the last pairs of digits of the powers of integer 3, that is, for the sequence 01,03,09,27,81,43,29,87,… (which is not random at all and does not verify the Kolmogorov’s theorem conditions).     

On the Ramanujan-Petersson conjecture for modular forms of half-integral weight

It is shown that a “character twist” of a growth estimate for certain weighted infinite sums of Kloosterman sums which is equivalent to the Ramanujan-Petersson conjecture for modular forms of half-integral weight, can easily be proved using Deligne’s theorem (previously the Ramanujan-Petersson conjecture for modular forms of integral weight).     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

A note on the last new vertex visited by a random walk

A “cover tour” of a connected graph G from a vertex x is a random walk that begins at x, moves at each step with equal probability to any neighbor of its current vertex, and ends when it has hit every vertex of G. The cycle C_n is well known to have the curious property that a cover tour from any vertex is equally likely to end at any other vertex; the complete graph K_n shares this property, trivially, by symmetry. Ronald L. Graham has asked whether there are any other graphs with this property; we show that there are not. © 1993 John Wiley & Sons, Inc.     

Serendipity

The aim of this short paper, is to show how serendipity was a key input in the research that led Ivar’s to two of his main contributions: proof of an old Hamiltonian systems conjecture using devices from the math eco tool box, then smart investigation of family’s budget decision process using symplectic geometry. Of course anyone is expected to say: “you mean: symplectic tools for Hamiltonians, and math eco toolkit for family budget.” Here is the point: these Ivar’s works illuminate how much serendipity creates unexpected brilliant results.     

Complexity of linear programming

The complexity of linear programming is discussed in the “integer” and “real number” models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation.Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all “reasonable” models of computation.     

Order of the smallest counterexample to Gallai’s conjecture

In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Zamfirescu conjectured that the smallest counterexample to Gallai’s conjecture is a graph on 12 vertices. We prove that Gallai’s conjecture is true for every connected graph G with α′(G) ≤ 5, which implies that Zamfirescu’s conjecture is true.     

An investment model with switching costs and the option to abandon

We develop a complete analysis of a general entry–exit–scrapping model. In particular, we consider an investment project that operates within a random environment and yields a payoff rate that is a function of a stochastic economic indicator such as the price of or the demand for the project’s output commodity. We assume that the investment project can operate in two modes, an “open” one and a “closed” one. The transitions from one operating mode to the other one are costly and immediate, and form a sequence of decisions made by the project’s management. We also assume that the project can be permanently abandoned at a discretionary time and at a constant sunk cost. The objective of the project’s management is to maximise the expected discounted payoff resulting from the project’s management over all switching and abandonment strategies. We derive the explicit solution to this stochastic control problem that involves impulse control as well as discretionary stopping. It turns out that this has a rather rich structure and the optimal strategy can take eight qualitatively different forms, depending on the problems data.     

Algorithmic complexity of Greenberg’s conjecture

Archiv der Mathematik - Let k be a totally real number field and p a prime. We show that the “complexity” of Greenberg’s conjecture ( $$\lambda = \mu = 0$$ ) is governed (under...