Graph Theory Geelen, Jim; Král', Daniel; Scott, Alexander
Oberwolfach reports,
02/2020, Letnik:
16, Številka:
1
Journal Article
Recenzirano
Graph theory is a rapidly developing area of mathematics. Recent years have seen the development of deep theories, and the increasing importance of methods from other parts of mathematics. The ...workshop on Graph Theory brought together together a broad range of researchers to discuss some of the major new developments. There were three central themes, each of which has seen striking recent progress: the structure of graphs with forbidden subgraphs; graph minor theory; and applications of the entropy compression method. The workshop featured major talks on current work in these areas, as well as presentations of recent breakthroughs and connections to other areas. There was a particularly exciting selection of longer talks, including presentations on the structure of graphs with forbidden induced subgraphs, embedding simply connected 2-complexes in 3-space, and an announcement of the solution of the well-known Oberwolfach Problem.
Interval branch-and-bound solvers provide reliable algorithms for handling non-convex optimization problems by ensuring the feasibility and the optimality of the computed solutions, i.e. ...independently from the floating-point rounding errors. Moreover, these solvers deal with a wide variety of mathematical operators. However, these solvers are not dedicated to quadratic optimization and do not exploit nonlinear convex relaxations in their framework. We present an interval branch-andbound method that can efficiently solve quadratic optimization problems. At each node explored by the algorithm, our solver uses a quadratic convex relaxation which is as strong as a semi-definite programming relaxation, and a variable selection strategy dedicated to quadratic problems. The interval features can then propagate efficiently this information for contracting all variable domains. We also propose to make our algorithm rigorous by certifying firstly the convexity of the objective function of our relaxation, and secondly the validity of the lower bound calculated at each node. In the non-rigorous case, our experiments show significant speedups on general integer quadratic instances, and when reliability is required, our first results show that we are able to handle medium-sized instances in a reasonable running time.
Graph Theory Diestel, Reinhard; Král', Daniel; Seymour, Paul
Oberwolfach reports,
10/2016, Letnik:
13, Številka:
1
Journal Article
Recenzirano
This workshop focused on recent developments in graph theory. These included in particular recent breakthroughs on nowhere-zero flows in graphs, width parameters, applications of graph sparsity in ...algorithms, and matroid structure results.
We show that plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) and transversal structures can be set in correspondence to certain (weighted) models of quadrant walks, ...via suitable specializations of a bijection due to Kenyon, Miller, Sheffield and Wilson. We then derive exact and asymptotic counting results. In particular we prove (computationally and then bijectively) that the number of plane bipolar posets on n + 2 vertices equals the number of plane permutations (i.e., avoiding the vincular pattern 2 14 3) of size n. Regarding transversal structures, for each v ≥ 0 we consider tn(v) the number of such structures with n + 4 vertices and weight v per quadrangular inner face (the case v = 0 corresponds to having only triangular inner faces). We obtain a recurrence to compute tn(v), and an asymptotic formula that for v = 0 gives tn(0) ∼ c (27/2) n n −1−π/arccos(7/8) for some c > 0, which also ensures that the associated generating function is not D-finite.
The adjacency matrix of a symplectic dual polar graph restricted to the eigenspaces of an abelian automorphism subgroup is shown to act as the adjacency matrix of a weighted subspace lattice. The ...connection between the latter and Uq(sl2) is used to find the irreducible components of the standard module of the Terwilliger algebra of symplectic dual polar graphs. The multiplicities of the isomorphic submodules are given.
Given a graph H, a graph G is called H-critical if G does not admit a homomorphism to H, but any proper subgraph of G does. Observe that K k−1-critical graphs are the standard k-(colour)-critical ...graphs. We consider questions of extremal nature previously studied for k-critical graphs and generalize them to H-critical graphs. After complete graphs, the next natural case to consider for H is that of the odd-cycles. Thus, given integers and k, ≥ k, we ask: what is the smallest order of a C 2 +1-critical graph of odd-girth at least 2k + 1? Denoting this value by η(k, C 2 +1), we show that η(k, C 2 +1) = 4k for 1 ≤ ≤ k ≤ 3 +i−3 2 (2k = i mod 3) and that η(3, C 5) = 15. The latter means that a smallest graph of odd-girth 7 not admitting a homomorphism to the 5-cycle is of order 15. Computational work shows that there are exactly eleven such graphs on 15 vertices.
We study the generating functions for cylindric partitions with profile (c_1,c_2,c_3) for all c_1,c_2,c_3 such that c_1+c_2+c_3=5. This allows us to discover and prove seven new A_2 Rogers–Ramanujan ...identities modulo 8 with quadruple sums, related with work of Andrews, Schilling, and Warnaar J. Amer. Math. Soc. 12 (1999), pp. 677–702.
We develop a statistical model for the testing of disease prevalence in a population. The model assumes a binary test result, positive or negative, but allows for biases in sample selection and both ...type I (false positive) and type II (false negative) testing errors. Our model also incorporates multiple test types and is able to distinguish between retesting and exclusion after testing. Our quantitative framework allows us to directly interpret testing results as a function of errors and biases. By applying our testing model to COVID-19 testing data and actual case data from specific jurisdictions, we are able to estimate and provide uncertainty quantification of indices that are crucial in a pandemic, such as disease prevalence and fatality ratios.
This article is part of the theme issue ‘Data science approach to infectious disease surveillance’.
A new class of premature, partial latin squares Euler, Reinhardt
Bulletin mathématiques de la Société des sciences mathématiques de Roumanie,
04/2024, Letnik:
67, Številka:
115
Journal Article
Combining two well-known types, we present a new class of partial latin squares whichare not completable and minimal with respect to this property.
PDF
